[리트코드(LeetCode)] 24. Swap Nodes in Paris - Python

leetcode.com/problems/swap-nodes-in-pairs/

Swap Nodes in Pairs - LeetCode

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

풀이

인접한 두 노드 간의 값을 스왑하는 문제로 노드의 개수가 홀수인 경우 마지막 남는 한 개의 노드는 그대로 두는 것 같다.

 

가장 기본적인 방법으로는 노드에 있는 값만 바꾸는 방법이다. 

    # 풀이 1. 값만 교환
    def swapPairs_value(self, head: ListNode) -> ListNode:
        node = head
        while node and node.next:
            node.val, node.next.val = node.next.val, node.val
            node = node.next.next

        return head

그러나, 이 방법은 해당 문제의 경우 하나의 값으로 구성된 단순한 연결 리스트이기 때문에 가능하지, 대개 연결 리스트는 복잡한 여러 가지 값들의 구조체로 구성되어 있어, 사실상 값만 바꾸는 것은 매우 어려운 일이라고 한다. 실용성과는 다소 거리가 있는 풀이법이다.

 

 

단순히 값만 바꾸는 것이 아니라 연결 리스트의 노드 자체를 바꾸는 방법을 모색해 보자.

다음 노드를 가리키는 포인터를 변경해주어야 하는데 바뀌는 노드는 두 개이지만 각 노드들은 앞, 뒤로 다른 노드들과 연결되어 있기 때문에 주의해야한다.

a - b - c - d 라는 연결리스트 중 b와 c를 바꾼다면 c는 b를 가리키고, b는 c의 다음인 d를 가리킨다. 그리고 b의 이전 노드인 a는 이제 c를 가리켜야한다.

while문을 통해 다음과 같이 반복 구조로 구현 가능하다.

 # 풀이 2. 반복 구조로 스왑
    def swapPairs_repeat(self, head: ListNode) -> ListNode:
        root = prev = ListNode() # 더미 노드
        prev.next = head

        # prev - head - tail - tail.next => prev - tail - head - tail.next
        while head and head.next:
            # tail이 head를 가리키도록 할당
            tail = head.next
            head.next = tail.next
            tail.next = head

            # prev가 tail을 가리키도록 할당
            prev.next = tail

            # 다음번 비교를 위해 이동
            head = head.next  # 원래 tail.next로 이동
            prev = prev.next.next  # prev.next는 tail, prev.next.next는 head. 즉, head.next의 이전 노드로 이동

        return root.next

 

 

위 풀이 방법을 재귀 구조로 개선할 수 있다. 재귀로 코드를 작성하면 반복 구조와 다르게 포인터 역할을 하는 변수가 하나만 있어도 충분하고, 더미 노드를 만들 필요가 없어 더 낮은 공간 복잡도로 풀이가 가능하다.

 # 풀이 3. 재귀 구조로 스왑
    # 반복 풀이와 달리 포인터 역할을 하는 변수가 하나만 있어도 충분함.
    # 더미 노드를 만들 필요가 없어 공간 복잡도가 낮음
    def swapPairs_recursive(self, head: ListNode) -> ListNode:
        if head and head.next:
            p = head.next
            # 스왑된 값 리턴 받음
            head.next = self.swapPairs_recursive(p.next)
            p.next = head
            return p
        return head

 

www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178

파이썬 알고리즘 인터뷰 - 교보문고