“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/swap-nodes-in-pairs/
입력 받은 연결 리스트를 페어 단위로 스왑하는 문제이다. [1,2,3,4]가 입력일 때 [2,1,4,3]이 출력이다.
페어 노드 a,b를 스왑한다면 b = a.next; a.next = a.next.next; a = b; 처럼 임시 변수를 두면 이해하기는 쉬운데 메모리 활용 면에서 더 좋은 방법이 있을 것이다. 그래도 생각나는대로 이번에도 재귀로 풀이 해보았다.
def swapPairs1(self, head: Optional[ListNode]) -> Optional[ListNode]:
def swap(node: ListNode) -> ListNode:
if not node or not node.next:
return node
temp = node.next
node.next = node.next.next
node, temp.next = temp, node
if node.next.next:
node.next.next = swap(node.next.next)
return node
return swap(head)이번에도 고전할 것이라는 예상과 다르게 리트코드에서 바로 accept 돼서 놀랐다. 코드가 간결하진 못해도, 노드 a와 b를 스왑하고 b의 next를 재귀 함수로 넘기는 풀이 방식은 틀리지 않았다. 오히려 반복문으로 만든다면 어떻게 될지 바로 떠오르지가 않았다.
그리고서 책의 재귀 방식 풀이를 보았는데 코드의 간결함에 놀랐다. 이것이 클래스의 차이인가. 다음이 그 코드이다.
def swapPairs2(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head and head.next:
pair = head.next
head.next = self.swapPairs2(pair.next)
pair.next = head
return pair
return headswapPair 함수를 바로 쓰기에 자신 없어서 내부 함수 swap을 일부러 만들었는데 그럴 필요가 없었다. head와 head.next가 비어 있지 않은지를 검사하는 것도 나는 더 꼬아버렸다. 정말 군더더기 없다.
반복문으로 풀이하는 방법은 그냥 책을 읽고 따라했다. 나는 왜 재귀가 더 직관적인 걸까.
def swapPairs4(self, head: Optional[ListNode]) -> Optional[ListNode]:
root = prev = ListNode()
prev.next = head
while head and head.next:
# b가 a(head)를 가리키도록 할당
b = head.next
head.next = b.next
b.next = head
# prev가 b를 가리키도록 할당
prev.next = b
# 다음 번 비교를 위해 이동
head = head.next
prev = prev.next.next
return root.next그리고 마지막으로 어떻게 보면 가장 단순한 방법인데, 두 노드의 값만 바꾸는 것이다.
def swapPairs3(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next:
cur.val, cur.next.val = cur.next.val, cur.val
cur = cur.next.next
return head책에 의하면 현실 세계에서는 정수로만 이루어진 노드보다는 복잡한 구조체인 경우가 많으므로 단순히 값만 스왑하는 것은 코딩 테스트에서의 하나의 풀이에 지나지 않을 것으로 보인다.