Linked List 유형 - 반전 처리

 

반전 처리

연결 리스트를 반전하는 것은 흔한 인터뷰 문제이지만, 다양한 문제를 해결하는 데 사용할 수 있는 기술이기도 합니다. 이유는 포인터를 이동시키는 방법에 대한 깊은 이해를 요구하기 때문입니다. 오늘은 이것에 대해 제대로 학습해봅시다.

 

가정

연결리스트 1 -> 2 -> 3 -> 4 가 있다고 가정하고, 이를 4 -> 3 -> 2 -> 1로 반환하고 싶다고 해봅시다.

 

현재 우리가 위치한 노드를 나타내는 포인터 curr이 있습니다. 처음에는 curr이 1에 위치하게 됩니다. 

반전을 위해서는 2가 -> curr을 가리키도록 해야 합니다. 여기서 문제는 curr = curr.next 로 이동하면, 단일 연결리스트이기 때문에 1에 대한 참조가 사라진다는 것입니다. 이를 해결하기 위해 이전 노드를 추적하는 또 다른 포인터 prev를 사용할 수 있습니다.

 

임의 노드 curr에서 curr.next = prev로 화살표의 방향을 바꿀 수 있습니다. 하지만 curr.next를 변경하면, 다음 노드에 대한 참조를 잃게 되겠져? 이를 해결하기 위해, 다른 포인터를 변경하기 전에 임시 변수 nextNode를 사용하여 다음 노드를 가리키도록 할 수 있습니다.

class ListNode {
    var val: Int
    var next: ListNode?

    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func reverseList(_ head: ListNode?) -> ListNode? {
    var prev: ListNode? = nil
    var curr = head

    while curr != nil {
        let nextNode = curr?.next  // 다음 노드를 잃지 않도록
        curr?.next = prev          // 포인터의 방향을 반전
        prev = curr                // 다음 노드를 위해 현재 노드를 prev로 설정
        curr = nextNode            // 다음으로 이동
    }

    return prev
}

 

while 루프는 n번 실행되며, 각 반복에서 수행되는 작업은 O(1)이기에, 시간 복잡도는 O(n)입니다.

몇 개의 포인터만 사용하고 있기 때문에 공간 복잡도는 O(1)입니다.

 

위 예제에서 거쳤던 사고 과정에 대해 정리해봅시다.

1. 현재 노드 curr에 있을 때, 그 노드의 next 포인터를 prev 노드로 설정해야 합니다.

• 이전 노드를 추적하기 위해 prev 포인터를 사용합니다.

2. prev 포인터도 매 반복마다 업데이트 되어야 합니다.

• curr.next를 업데이트 한 후, 다음 노드를 준비하기 위해 prev = curr로 설정합니다.

3. 만약 curr.next = prev로 설정하면, 원래 curr.next에 대한 참조를 잃게 됩니다.

• 원래 curr.next에 대한 참조를 유지하기 위해 nextNode를 사용합니다.

 

예제 1

• 연결 리스트의 헤드가 주어지면, 노드를 쌍으로 교환해야 합니다.
• 1 -> 2 -> 3 -> 4 -> 5 -> 6 가 주어질 경우, 2 -> 1 -> 4 -> 3 -> 6 -> 5 를 반환해야 합니다.

 

방법

단계 별로 필요한 작업을 나누어 보겠습니다. (첫 번째 쌍의 노드를 A -> B로 가정)

 

1. head가 노드 A에 있을 때, 우리는 노드 B가 A를 가리키도록 해야 합니다.

• 이를 위해 head.next.next = head 를 사용하면 됩니다.

2. 하지만 B.next를 변경하면, 나머지 리스트에 대한 참조를 잃게 됩니다.

• 1단계의 변경을 적용하기 전에, nextNode = head.next.next를 사용하여 포인터를 저장합니다.

 

참고

head.next.next는 할당 연산자의 앞에 있을 때와 뒤에 있을 때가 다르게 사용됩니다.

앞에 있을 경우, head.next 의 다음 노드를 변경하고, 뒤에 있을 경우 head.next의 다음 노드를 참조합니다.

 

 

3. 이제 B가 A를 가리키게 되었습니다. 다음 C, D로 이동해봅시다. A는 여전히 B를 가리키고 있기 때문에 바로 다음 노드로 이동하게 되면, A에 대한 참조를 잃게 됩니다.

• A를 다른 포인터에 저장하여 prev = head로 합니다. (아직 head를 변경하지 않았으므로 이는 여전히 A를 가리킴)
• 다음 쌍으로 이동하려면 head = nextNode를 실행해야 합니다.

 

4. C -> D 로 이동한 후, A가 D를 가리키도록 해야 합니다.

• 이제 헤드가 C에 있고, prev가 A에 있으므로 prev.next = head.next를 실행할 수 있습니다.

 

5. A, B가 완료되었습니다. B는 A를 가리키고, A는 D를 가리킵니다. 1~4 단계를 통해 A, B를 완성시켰죠? 이 단계를 반복적으로 수행하면 나머지도 스왑할 수 있습니다. 하지만 마지막에 무엇을 반환해야 할까요?

• 모든 짝이 완료되면, B를 반환해야 합니다. 하지만 B에 대한 참조는 오래전에 까먹었져?
• 알고리즘을 시작할 때, B를 더미 노드에 저장하여 이 문제를 해결할 수 있습니다.

 

6. 노드가 홀수일 경우에는 어떻게 될까요? 4단계에서 A.next를 C.next로 설정했습니다. 노드가 3개만 있을 경우, C.next는 null이 됩니다.

• 다음 짝으로 이동하기 전에 head.next = nextNode로 설정합니다. A.next를 C로 설정하는 것입니다.
• 다음 짝이 남아있을 경우, 다음 교환에서 4단계가 이를 덮어씁니다.
• 2단계에서 head.next.next를 사용하므로, while 루프 조건이 head와 head.next를 모두 확인해야 합니다. 즉, 리스트에 노드가 하나만 남아 있으면 현재 반복 후 while 루프가 종료됩니다.
• 예를 들어, A -> B -> C -> D인 경우를 고려해봅시다. 어느 순간, 우리는 B <-> A C -> D를 얻게 됩니다. 여기서 6단계를 수행하면, B -> A -> C -> D가 됩니다. C, D가 서로 교환하기 시작할 때, 4단계가 A.next를 D로 설정하여 6단계에서 한 작업을 덮어씁니다. 하지만 D가 존재하지 않으면 반복이 종료됩니다. 이 경우, B -> A -> C가 됩니다.

 

요약

1. A -> B -> C -> ...를 A <-> B C -> ...로 스왑해야합니다.

2. 현재 짝을 넘어 리스트의 나머지 부분에 접근할 수 있도록 head.next.next (C)에 대한 참조를 저장합니다.

3. 이제 A <-> B가 리스트의 나머지 부분에서 분리되었으므로 나중에 연결할 수 있도록 A에 대한 포인터를 저장합니다. 이후 다음 짝으로 이동합니다.

4. 이전 짝을 리스트의 나머지 부분과 연결합니다. 이 경우 A -> D로 연결합니다.

5. 반환하고자 하는 것을 참조하기 위해 더미 포인터를 사용합니다.

6. 노드의 수가 홀수일 때를 처리합니다.

 

중요한 점은 이 단계의 순서는 풀이를 위한 시간 순서가 아니라는 것입니다. 단지 문제의 요구사항을 고려하기 위한 생각할 수 있는 순서입니다.

class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        // 엣지 케이스 확인: 연결 리스트에 노드가 0개 또는 1개인 경우, 그대로 반환
        if head == nil || head?.next == nil {
            return head
        }

        let dummy = head?.next          // Step 5
        var prev: ListNode? = nil       // Step 3 초기화
        var curr = head                 // 현재 노드를 head로 설정

        while current != nil && current?.next != nil {
            if prev != nil {
                prev?.next = curr?.next      // Step 4: A.next -> D로 
            }
            prev = curr                      // Step 3: Prev를 현재 값으로

            let nextNode = curr?.next?.next  // Step 2: C에 대한 참조
            curr?.next?.next = curr          // Step 1: B.next -> A로

            curr?.next = nextNode            // Step 6: A.next -> C로  // 만약 D가 없을 경우(홀수)를 대비하여
            curr = nextNode                  // Step 3: C로 이동
        }

        return dummy
    }
}

 

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1) 입니다.

이렇게 연결 리스트 문제를 마주할 때는 문제를 분해해보세여. 우리가 해야할 일과 이를 달성하기 위해 필요한 작업들을 나열해보세여. 위에서 보았듯이, 단계를 생각하는 순서가 반드시 수행되어야 하는 순서와 동일하지는 않습니다.

 

 

 

예제 2

• 최대 짝의 합을 구하는 문제입니다. 짝은 첫 번째와 마지막 노드, 두 번째와 두 번째 마지막 노드, 세 번째와 세 번째 마지막 노드 등으로 구성됩니다.
• 길이가 짝수인 n의 연결 리스트에서, 0 <= i <= (n / 2) - 1 인 경우에 i번째 노드(0부터 시작하는 인덱스)는 (n - 1 - i) 번째 노드의 쌍둥이로 정의됩니다.
• 예를 들어, n = 4인 경우, 0번째 노드는 3 번째 노드의 쌍둥이이며, 1번째 노드는 2번째 노드의 쌍둥이 입니다. 이는 n = 4인 경우에 쌍둥이를 가진 유일한 노드들입니다. 쌍둥이 합은 노드와 그 쌍둥이 노드의 합으로 정의됩니다.
• 길이가 짝수인 연결 리스트의 head가 주어졌을 때, 연결 리스트의 최대 쌍둥이 합을 반환하세요.

 

예시 1

• head = [5, 4, 2, 1]
• 정답: 6
• 0번째 노드와 1번째 노드는 각각 3번째 노드와 2번째 노드의 쌍둥이 입니다. 모두 쌍둥이 합이 6입니다.

 

예시 2

• head = [4, 2, 2, 3]
• 정답: 7
• 이 링크드 리스트에서 쌍둥이가 있는 노드들은 다음과 같습니다
  • 0번째 노드는 3번째 노드의 쌍둥이로, 쌍둥이 합은 4 + 3 = 7입니다.
  • 1번째 노드는 2번째 노드의 쌍둥이로, 쌍둥이 합은 2 + 2 = 4입니다.
  • 따라서, 링크드 리스트의 최대 쌍둥이 합은 max(7, 4) = 7입니다.

 

예시 3

• head = [1,100000]
• 정답: 100001
• 링크드 리스트에 있는 쌍둥이를 가진 유일한 노드는 1 + 100000 = 100001입니다.

 

방법

1. Fast & Slow 를 통해 링크드 리스트의 중간을 찾습니다.

2. 링크드 리스트의 중간에 도달하면, 반전을 수행합니다. 리스트의 두 번째 절반만 반전합니다.

3. 두 번째 절반을 반전한 후, 모든 노드는 쌍의 노드와 n / 2 간격이 됩니다.

4. 이를 염두에 두고, slow에서 n / 2 앞선 또 다른 fast 포인터를 생성합니다. 이제 head부터 n / 2 번 반복하여 모든 쌍의 합을 찾으면 됩니다.

 

먼저 스스로 코드를 짜보셔요.

이전 예제와는 달리, 반전은 문제의 전체 포인트가 아니라 그냥 더 나은 해결책에 도달하기 위한 도구입니다. 

class Solution {
    func pairSum(_ head: ListNode?) -> Int {
        var slow = head
        var fast = head
        
        // 중간 노드를 찾음
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
       
        var curr = slow
        var prev: ListNode? = nil
        
        // 중간 노드부터 반전 시작
        while curr != nil {
            let nextNode = curr?.next  // 다음 노드에 대한 참조 유지
            curr?.next = prev          // 이전 노드로 방향 전환
            prev = curr                // 현재 노드로 변경 (다음 노드에서 방향 전환을 위해 사용)
            curr = nextNode            // 다음 노드로 이동
        }
        
        slow = head  // slow는 헤드로 원위치
        fast = prev  // n/2 위치에 있는 노드
        var ans = 0  // 답변을 위한 변수
        
        // fast.next != nil 조건은 제거.
        while fast != nil {
            ans = max(ans, slow!.val + fast!.val)
            slow = slow?.next
            fast = fast?.next
        }

        return ans
    }
}

 

이외에도 연결 리스트는 다른 용도로 사용되기도 합니다.

해시에서 충돌 회피를 위한 기법으로 체이닝에 사용되기도 하며, 후에 deque라는 자료 구조에 대해 알아볼 때도 사용될 수 있습니다. 

대부분 연결 리스트 문제에 트릭보다는 포인터를 이동하는 방법에 대한 깊은 이해가 필요합니다. 연습을 많이 해보셔요

 

 

 

 

Reference

https://leetcode.com/