17. Swap Nodes in Pairs

리트코드

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

1. 값만 교환 (24ms)

# 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:
        cur = head
        
        while cur and cur.next:
            # 값만 교환
            
            cur.val, cur.next.val = cur.next.val, cur.val
            cur = cur.next.next
            
        return head

• 진관적인 방법인 풀이로, 다소 변칙적인 방법이기도 하다.

• 연결리스트의 노드를 변경하는게 아닌, 구조는 그대로 유지하되 값만 변경하는 방법이다.

• 대개 연결 리스트는 복잡한 여러가지 값들의 구조체로 구성되어 있고, 사실상 값만 바꾸는 것은 매우 어려운 일이기 때문이다.

  • 그러나, 이 문제에서는 단 하나의 값으로 구성된 단순한 연결 리스트이고, 값을 바꾸는 정도는 어렵지 않게 가능하다.

  
  
  

2. 반복 구조로 스왑 (20ms)

# 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
            

• 연결리스트 자체를 바꾸는 일은 생각보다 다소 복잡한 문제다.

  • 1->2->3->4->5->6인 연결 리스트가 있을 경우, 3->4를 4->3으로 바꾼다고 할 때, 단순히 둘만 바꾼다고 끝나는 문제가 아니라, 그 앞인 2가 가리키는 연결 리스트와 5로 연결되는 연결 리스트도 다 같이 변경해야 하기 때문이다.

• b가 a를 가리키고, a는 b의 다음을 가리키도록 변경한다.

• a의 이전 노드 prev가 b를 가리키게 하고, 다음번 비교를 위해 prev는 두 칸 앞으로 이동한다. 그리고 다시 다으번 교환을 진행할 것이다.

• 연결리스트의 head를 가리키는 노드가 직접 바뀌는 풀이이므로, head를 리턴하지 못하고 그 이전 값을 root로 별도로 설정한 다음 root.next를 리턴하게 했다.

3. 재귀 구조로 스왑 (20ms)

# 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
            

• 반복풀이와 달리 포인터 역할을 하는 p변수는 하나만 있어도 충분하며, 더미 노드를 만들 필요도 없이 head를 바로 리턴할 수 있어 공간 복잡도가 낮다.

• p는 head.next가 되고, p.next는 head가 된다.

• 그 사이에 재귀 호출로 계속 스왑된 값을 리턴받게 된다.

• 다른 연결 리스트 문제들의 풀이와 마찬가지로, 실제로는 백트래킹되면서 연결리스트가 이어지게 된다.