[알고리즘] 페어의 노드 스왑

페어의 노드 스왑

내 풀이

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        tail = head

        while tail and tail.next:
            tail.val, tail.next.val = tail.next.val, tail.val
            tail = tail.next.next

        return head

처음에는 노드 자체를 스왑해야한다는 생각에 사로 잡혀서 값만 바꿀 생각을 하지 못했다.

책 풀이

사실 값만 바꾸는 풀이는 정석적인 풀이가 아니다. 노드가 단순한 구조가 아니라면 복잡할 것이다.

        root = prev = ListNode(None)
        prev.next = head
        while head and head.next:
            # b가 a(head)를 가리키도록 할당
            b = head.next
            head.next = b.next
            b.next = head
            
            prev.next = b
            
            head = head.next
            prev = prev.next.next
        return root.next

복잡해 보이지만 그림을 그려가며 이해하면 충분히 따라 갈 수 있다.

좋은 웹페이지 즐겨찾기