ch8 24 페어의 노드 스왑

• 문제
• 풀이
  • 값만 스왑
    • 생각
    • 코드
  • 반복 구조로 스왑
    • 생각
    • 실패한 코드
    • 책 풀이
  • 재귀 구조로 스왑
    • 생각
    • 책 풀이

문제

Given a linked list, swap every two adjacent nodes and return its head.

풀이

값만 스왑

생각

• 노드 자체를 바꾸기보다는 값만 바꾸는 것은 어떨까?라고 생각
• 하지만 실제로는 노드의 구조과 더 복잡하기 때문에, 실제 코딩에서 값만 바꾸는 것은 현실성 없다

코드

def first(self, head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    node_curr = head
    # 1. 반복: 두 개씩 스왑하므로, 현재의 다음 노드가 있는 동안 반복
    while node_curr.next:
        # 2. 노드의 스왑: 값만 바꾸면 되지 않을까?
        node_curr.val, node_curr.next.val = node_curr.next.val, node_curr.val
        # 3. 현재 노드는 다다음 노드로 변경
        if node_curr.next.next:
            node_curr = node_curr.next.next
        else:
            break

    return head

반복 구조로 스왑

생각

• 노드만 갈아끼워주면 되지 않을까? 라고 간단하게 생각
• 하지만 python 오브젝트들이 call by reference로 호출되며 변수에 할당되는 것들이 실제로는 해당 값을 저장하고 있는 주소여서 어떻게 반복할 것인가가 헷갈렸다

실패한 코드

    # 실패
    def second(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        # 1. 반복: 두 개씩 스왑하므로, 현재의 다음 노드가 있는 동안 반복
        # ListNode는 Python Object로 같은 메모리 주소를 가리킨다(by reference)
        # node_curr에는 head에 대한 `주소` 저장
        node_curr = head
        while node_curr and node_curr.next:
            # 2. 스왑
            # - 현재 노드 임시 저장
            tmp = node_curr
            # - 다음 노드를 현재 노드로
            node_nnext = tmp.next.next
            node_curr = tmp.next
            # - `이전 현재 노드`를 다음 노드로
            node_curr.next = tmp
            # - `이전 다음 노드`의 다다음 노드가 있었다면, `현재 다음 노드`의 다음 노드로 치환
            node_curr.next.next = node_nnext
            node_curr = node_curr.next.next

        return head

책 풀이

def third(self, head: ListNode) -> ListNode:
    # root: 풀이에서 head가 계속 변경되므로, root.next로 결과 값을 반환한다
    # prev: 다음 비교를 위해 두 칸씩 이동시킬 변수
    root = prev = ListNode(None, head)

    # head = 1 -> 2 -> 3 -> 4
    # root: None -> 1 -> 2 -> 3 -> 4
    # prev: None -> 1 -> 2 -> 3 -> 4
    while head and head.next:
        # tmp: 값이 실제로 스왑되는 변수
        # 한 쌍에서 다음 노드를 앞으로 끌어 올린다
        # tmp = 2 -> 3 -> 4
        tmp = head.next
        # 다다음 노드를 원래 head의 다음 노드로 할당한다
        # tmp.next = 3 -> 4
        # head = 1 -> 3 -> 4
        head.next = tmp.next
        # 앞으로 끌어 올려진 `이전의 다음 노드`에 head를 붙인다
        # tmp.next = 1 -> 3 -> 4
        # tmp = 2 -> 1 -> 3 -> 4
        tmp.next = head

        # prev = None -> 1 -> 2 -> 3 -> 4
        # prev = None -> 2 -> 1 -> 3 -> 4
        prev.next = tmp

        # head = 3 -> 4
        head = head.next
        # prev = 1 -> 3 -> 4
        prev = prev.next.next

    return root.next

재귀 구조로 스왑

생각

• 여기까지는 생각을 못했다.
• 노드의 끝이 None이므로 기저 케이스를 잡기는 쉬울 듯 하다
• 다만 코드가 훨씬 간단하긴 하지만, 직관적으로 와닿지는 않았다
• 그리고 재귀는 가독성도 떨어지고 기저 케이스를 잘못 잡으면 문제가 커서 가급적 피하고 싶다

책 풀이

# 재귀 풀이 방식. 가장 끝에서부터 스왑하면서 올라온다
def fourth(self, head: ListNode) -> ListNode:
    # p = 2
    #   tmp = 4 -> 3 -> None
    #       head = 1 -> 4 -> 3 -> None
    #           p = 2 -> 1 -> 4 -> 3 -> None
    #  2 -> 1 -> 4 -> 3
    if head and head.next:
        # p는 우선 다음 값으로 할당하고
        p = head.next
        # 스왑된 값을 리턴 받는다
        tmp = self.fourth(p.next)
        # 스왑된 tmp를 head의 다음 값에 넣고
        head.next = tmp
        # 헤드를 앞서 스왑된 p의 다음 값에 넣는다
        p.next = head
        return p

    return head