파이썬 알고리즘 인터뷰 17번 페어 노드 스왑 (리트코드 24번)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Solution

class Solution:
    def swap(self, head: Optional[ListNode]):
        if head.next is None or head.next.next is None:
            return
        
        next = head.next
        next_next = head.next.next
        
        head.next = next_next
        next.next = next_next.next
        next_next.next = next

        self.swap(next)
        
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        start = ListNode()
        start.next = head
        self.swap(start)
        return start.next

… A → B → C → D가 있고 현재의 head가 A라고 할 때 B와 C의 위치를 바꿔야한다. 따라서 A → C, C → B, B → D로 연결을 해주었다. 연결 리스트가 끊어지면 안되므로 swap 대상의 하나 전에서 바라보면서 스왑을 해주는 것이 포인트였다.