[Leetcode] 리트코드 - 페어의 노드 스왑(swap-nodes-in-pairs) 파이썬(python) 풀이

페어의 노드 스왑

문제

문제링크
연결 리스트를 입력받아 페어(pair) 단위로 스왑하라

입력
1→2→3→4

출력
2→1→4→3

코드

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        root = prev = ListNode(None)
        prev.next = head
        while head and head.next:
            #fixme b가 head를 가리키도록 할당
            b = head.next
            head.next = b.next
            b.next = head

            #fixme prev가 b를 가리키도록 할당
            prev.next = b

            #fixme 다음번 비교를 위해 이동
            head = head.next
            prev = prev.next.next # fixme 3, 4가 4, 3으로 바꼈을 때 1, 2 쪽의 2를 4와 연결시키기 위해서는 prev가 꼭 필요하고 매 반복마다 순간 바꿔주어야 한다.

        return root.next

재귀함수 코드

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head and head.next:
            p = head.next
            head.next = self.swapPairs(p.next)
            p.next = head
            return p #fixme if 문에서 종료하게 되면 p를 반환하고 바로 함수가 종료됨
        return head

풀이

그림으로 이해하니 편하다.

root = prev = ListNode(None)
prev.next = head

#fixme b가 head를 가리키도록 할당
b = head.next
head.next = b.next
b.next = head

#fixme prev가 b를 가리키도록 할당
prev.next = b

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

head와 head.next가 None가 아닐 때까지 반복한다.

재귀함수 과정

헷갈렸던 부분

prev = prev.next.next
3, 4가 4, 3으로 바꼈을 때 1, 2 쪽의 2를 4와 연결시키기 위해서는 prev가 꼭 필요하고 매 반복마다 바꿔주어야 한다.

재귀함수 풀이에서 if 문에서 종료하게 되면 p를 반환하고 바로 함수가 종료된다. head가 아닌 p가 반환된다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]