[LeetCode,Python] 24. 페어의 노드 스왑(Swap Nodes in Pairs)

연결 리스트를 입력받아 페어 단위로 스왑 하라.

 

Input: head = [1,2,3,4]

Output: [2,1,4,3]

 

 

 

 

1. 내가 직접 푼 풀이

 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        root = head
 
        while head and head.next:
            head.val, head.next.val = head.next.val, head.val
            head = head.next.next
        return root

 

해설:

 

단순하게 연결 리스트의 값을 교환했다.

코드는 매우 단순하니까 생략함.

 

 

 

 

 

2. 연결 리스트의 연결을 바꾼 코드

 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        root = head
        prev = ListNode(None)
        prev.next = head
        while head and head.next:
            head.next, head.next.next = head.next.next, prev.next
            prev = prev.next
            head = head.next
        return root

 

해설:

 

연결 리스트의 연결을 바꿔가며 진행해봤다.

root는 최종적으로 스왑 된 연결 리스트를 출력하기 위해 지정하였고

prev를 통해 왼쪽 페어를 지정할 수 있게 하였다.

개인적으로 아래의 '반복 구조로 스왑'보다 내가 더 깔끔한 것 같은데

혹시나 논리적 오류가 있을 것 같으니

(아직 나는 나를 못 믿어 ㅎ)

허점이 있으면 댓글 남겨주세요!

 

 

 

 

 

** 깔끔 답안 **

 

3. 반복 구조로 스왑

 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> 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

 

해설:

 

위 예시를 기준으로 했을 때

prev의 역할은 1->4를 연결시키기 위함이다.

 

손으로 천천히 관계를 그려나가다보면 이해가 된다.

나는 처음에 prev가 왜 필요한지 몰랐는데

prev가 없으면 뒤집어진 페어간에 연결이 안된다..

 

아 그리고 굳이 왜 9번 줄을 설정했냐면

만약 입력값이 [1]처럼 노드가 하나뿐이라면

반복문을 실행하지 않기 때문에 리턴 값에서 문제가 생긴다.

 

while문에 넣고 페어마다 반복적으로 나아가려면 첫번째 페어부터 마지막 페어까지 똑같은 형식이 적용되도록 하는 것이 중요하다. 첫번째 페어에서는 prev를 초기화해야되니 머리를 잘 써봐라. 뭐라 말하기 어렵다....

 

 

 

※ 몇달 뒤에 다시 와서 풀어보니 다 까먹었다 ㅋ..

이런 문제를 풀때는 연결해야하는 노드 사이를 고려해서 변수를 설정해주는 것이 좋을 것 같다.

위 코드에서도 보면 b를 만든 이유는 prev를 항상 짝의 첫번째에 세팅해두기 위함인데

b를 설정하지 않으면 prev가 짝의 첫번째로 갈 수가 없다.

 

 

 

 

4. 재귀 구조로 스왑

 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = 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
        return head

해설:

 

지금까지 재귀 함수를 써오면서 느낀 건

(아직 10%도 제대로 활용 못하지만)

대략적인 점화식을 생각하고

함수를 재귀하는 부분을 제외하면 마지막의 한정된 부분만 생각해서 코드를 짜야한다.

 

 

예를 들어

지금 같은 경우,

우리가 마지막 페어에 와 있다 생각하고

(1->2->3->4->5라 하면 head.val이 4인 상황)

 

p = head.next(스왑 대상 지정)

head.next = ~~~~ 로 p 다음 대상을 가리킨다.

그리고 p.next = head를 가리킨다.

 

그리고 생각을 한다.

 

 

"일단 head와 p의 다음 대상은 가리켜 놨고 지금 마지막 페어에 있으니까 재귀 함수가 반환될 때 head를 반환해야 될거고... 페어 초기에 있다면 다음 페어가 스왑될 수 있도록 재귀를 구성해야겠군"

 

 

뭔 개소리인지 나도 잘 모르겠다.

후에 재귀함수 마스터가 되면 다시 수정하러 올 테니 이 문제가 이해가 안 된다면 댓글을 남겨줘라!

미래의 알고리즘 고수가 된 내가 답변을 달아주겠다.

 

 

 

 

 

출처: 파이썬 알고리즘 인터뷰(박상길 지음, 정진호 일러스트) 출판사[책만]