728x90
반응형
https://leetcode.com/problems/swap-nodes-in-pairs/
오랜만에 만난 linked list 의 문제입니다.
Linked list 관련 개념과 문제들은 아래에서 참고 가능합니다
2022.09.15 - [‼ ERROR RECORD] - Leetcode 02. Add Two Numbers
2022.09.14 - [Data Structure & Algorithm] - Linked List 총정리
짝수 번째에서 이웃한 노드와 값의 위치를 교환하는 문제인데요
여러 풀이를 보면서 linked list라는 구조의 특성에서 어떻게 값 교환을 하는지 보겠습니다.
변수 및 위치 swap 풀이)
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return head
prev, cur, ans = None, head, head.next
while cur and cur.next:
adj = cur.next
if prev: prev.next = adj
cur.next, adj.next = adj.next, cur
prev, cur = cur, cur.next
return ans or head
유사한 iterative 풀이)
def swapPairs(self, head):
dummy = p = ListNode(0)
dummy.next = head
while head and head.next:
tmp = head.next
head.next = tmp.next
tmp.next = head
p.next = tmp
head = head.next
p = tmp.next
return dummy.next
Recursion 활용 풀이 )
def swapPairs(self, head):
if head and head.next:
tmp = head.next
head.next = self.swapPairs(tmp.next)
tmp.next = head
return tmp
return head
이렇게 이전 값과 현재 값을 가지고 비교하는 경우에는 prev 변수와 curr 변수의 적절한 사용을 통해 풀이하는 경우가
많은 것 같습니다. 앞으로 문제를 보면 하나의 힌트로 사용할 수도 있을 것 같네요
728x90
반응형
'‼ ERROR RECORD' 카테고리의 다른 글
Leetcode 189. Rotate Array (O(1) 제약조건) (0) | 2022.10.27 |
---|---|
Leetcode 24. Pathsum2 (DFS, Backtracking) (0) | 2022.10.26 |
Leetcode 211. Design Add and Search Words(Trie+DFS) (0) | 2022.10.20 |
Leetcode 310. Minimum Height Trees (0) | 2022.10.11 |
Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal (1) | 2022.10.06 |
댓글