연결 리스트 (Python Algorithm interview 8장)

파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다.

페어의 노드 스왑

입력

1 -> 2 -> 3 -> 4

출력

2 -> 1 -> 4 -> 3

값만 교환

def swapPaire(self, head):
    cur = head

    while cur and cur.next:
        # 값만 교환
        cur.val, cur.next.val = cur.next.val, cur.val
        cur = cur.next.next
    return head

연결 리스트의 노드를 변경 하는 것이 아닌 노드의 값을 변경하는 방식이다. 연결 리스트는 노드의 연결로 이뤄지기 때문에 단순히 노드의 값만 변경하는 것은 실용적이지 않다.

반복 구조로 스왑

def swapPairs(self, head: ListNode):
    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가 b를 가리키도록 할당
        prev.next = b

        # 다음번 비교를 위해 이동
        head = head.next
        prev = prev.next.next
    return root.next

b가 a(head)를 가리키도록 하고 a는 b의 next를 가리킨다. a의 이전 노드 prev가 b를 가리키게 하고, prev를 두 칸 이동한다.

재귀 구조로 스왑

def swapPairs3(self, head:ListNode):
    if head and head.next:
        p = head.next
        #스왑된 값 리턴 받음
        head.next=self.swapPairs3(p.next)
        p.next= head
        return p
    return head

포인터 역할을 하는 p 하나만 사용해서 문제를 해결한다. 반복 구조를 재귀로 개선하였다.