LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이 아이디어

문제의 조건

떠올릴 수 있는 가장 쉬운 방법은 node들의 순서를 조정하지 않고 그냥 node 안에 값만 바꾸는 것이다. 하지만 문제의 조건에는 “You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)”라고 적혀있다. 값을 바꾸지 말고 node 자체의 순서를 바꾸는 방식으로 문제를 풀라는 것이다.

2개의 node의 순서를 바꾸기 위한 과정

단방향 링크드리스트에서 연속된 2개의 node의 순서를 바꾸기 위해서는 수 node의 next 뿐만 아니라 두 node의 앞에 존재하는 node의 next도 바꾸어 주어야 한다. 나머지 로직은 코드의 주석을 참고해주기를 바란다.

코드

class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        // 링크드리스트에 node가 없거나 node가 1개만 있는 경우
        if head?.next == nil { return head }
        
        // 현재 swap할 node 2개의 이전에 위치한 node
        var before: ListNode? = nil
        // swap할 대상 node 2개
        var pair1 = head
        var pair2 = head?.next
        
        // 2번째 node가 새로운 head가 되므로 참조를 미리 저장해둔다.
        let ans = pair2
        
        while pair1 != nil, pair2 != nil {
            // 현재 swap할 node 2개의 뒤에 있는 node
            let after = pair2?.next

            // 1. before의 next에 pair2
            before?.next = pair2
            // 2. pair2의 next에 pair1
            pair2?.next = pair1
            // 3. pair 2의 next에 after
            pair1?.next = after
            
            // 다음 swap할 대상으로 pair 이동
            before = pair1
            pair1 = pair1?.next
            pair2 = pair1?.next
        }
        
        return ans
    }
}

재귀함수를 이용한 풀이

문제 풀이 아이디어

조금 이해하기는 어렵지만 코드는 훨씬 깔끔한 풀이다. 일단 우리가 원하는 동작을 그림으로 그려보면 아래와 같다. 일단 전체 리스트를 리스트, 그리고 현재 스왑할 2개의 node(1, 2)를 제외한 나머지 리스트를 리스트’이라고 부르겠다. 리스트’는 3을 head로 하는 리스트이다. 이렇게 리스트를 구분해서 봤을 때 모든 스왑을 마무리 했을 때 리스트의 형태는 어떻게 되었을까?

일단 스왑할 2개의 node는 스왑이 되어서 1 → 2가 2→ 1이 되었다. 그렇다면 1 뒤는 어떻게 될까? 이는 기존에 3을 head로 하는 리스트’의 스왑한 버전이라고 할 수 있다. 따라서 1의 next는 리스트’를 스왑한 버전의 head가 된다. 따라서 아래 코드처럼 재귀함수의 형태로 구현할 수 있다.

코드

class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        if head != nil, head?.next != nil {
            // 현재 head와 swap할 대상
            let toSwap = head?.next
            // 현재 head의 next는 swap할 대상의 next를 head로 하는 링크드리스트(= 리스트')를 스왑한 결과
            head?.next = swapPairs(toSwap?.next)
            // head와 swap의 위치변경
            toSwap?.next = head
            
            // toSwap되어서 head가 바뀜
            return toSwap
        }
        
        // head가 더 이상 존재하기
        return head
    }
}