Linked List 유형 - Fast & Slow

 

연결 리스트 유형의 풀이 방법 중 하나는  Fast와 Slow라는 두 개의 포인터를 사용하는 것입니다. 두 포인터는 나란히 움직이지 않고, 다른 '속도'로 이동하거나, 다른 위치에서 반복을 시작하는 등의 차이를 의미합니다.

 

다른 '속도'로 이동한다고 했다면, 일반적으로 Fast 포인터는 반복 당 두 노드를 이동하고, Slow 포인터는 반복 당 하나의 노드를 이동합니다. 코드를 봅시다.

// head는 링크드 리스트의 첫 번째 노드를 가리킵니다.
func fn(head: ListNode?) {
    var slow = head
    var fast = head

    // fast가 nil이 아니고 && fast.next가 nil이 아닐 때까지
    while fast != nil && fast?.next != nil {
        // 여기서 필요한 작업을 수행합니다.
        
        // slow 포인터는 한 노드 앞으로 이동합니다.
        slow = slow?.next
        
        // fast 포인터는 두 노드 앞으로 이동합니다.
        fast = fast?.next?.next
    }
}

 

fast 포인터가 마지막 노드에 있을 경우, fast.next가 null이 되기 때문에 while 조건에서 fast.next도 확인해야 합니다. 

그렇지 않으면, null.next를 시도하기 때문에 오류가 발생할 수 있겠져?

이제 예시를 살펴봅시다.

 

 

예제 1

• 노드의 수가 홀수인 링크드 리스트의 머리 노드인 헤드가 주어졌을 때, 중간에 있는 노드의 값을 반환하세요
• 예를 들어, 1 -> 2 -> 3 -> 4 -> 5 를 나타내는 링크드 리스트가 주어지면? 3을 반환합니다.

 

방법

이 문제를 해결하는 쉬운 방법은 링크드 리스트를 배열로 변환한 다음, 배열의 중간에 있는 숫자를 반환하는 것입니다.

// head는 링크드 리스트의 첫 번째 노드를 가리킵니다.
func fn(head: ListNode?) -> Int? {
    var array: [Int] = []
    var current = head
    
    // 링크드 리스트를 배열로 변환
    while current != nil {
        array.append(current!.data)
        current = current?.next
    }
    
    // 배열의 중간에 있는 값을 반환합니다.
    return array[array.count / 2]
}

 

하지만 이 방법은 일명 야매죠? 

 

또 다른 방법은 더미 포인터를 사용하여 연결 리스트를 한 번 순회하여 길이를 찾고, 다시 머리부터 중간을 찾을 때까지 한번 더 순회하는 것입니다.

func getMiddle(head: ListNode?) -> Int? {
    // 리스트의 길이를 저장할 변수 초기화
    var length = 0
    var dummy = head

    // 더미 포인터를 사용하여 리스트의 길이를 계산
    while dummy != nil {
        length += 1
        dummy = dummy?.next
    }

    // 리스트의 중간 지점까지 이동
    var current = head
    
    for _ in 0 ..< (length / 2) {
        current = current?.next
    }

    // 중간 노드의 값을 반환
    return current?.val
}

 

 

이보다 더 좋은 방법은 위에서 배운 Fast & Slow 포인터를 사용하는 것입니다.

Fast가 Slow보다 두 배 빠르게 움직인다면, Fast가 끝에 도달할 때, Slow는 절반 속도이기 때문에 중간 지점에 도달하게 될 것 입니다.

func getMiddle(head: ListNode?) -> Int? {
    // 느린 포인터와 빠른 포인터를 초기화
    var slow = head
    var fast = head

    // 빠른 포인터가 끝에 도달할 때까지 반복
    while fast != nil && fast?.next != nil {
        slow = slow?.next        // 느린 포인터는 한 노드씩 이동
        fast = fast?.next?.next  // 빠른 포인터는 두 노드씩 이동
    }

    // 느린 포인터가 중간 노드에 도달했을 때 그 값을 반환
    return slow?.val
}

 

공간복잡도는 O(1)이며, 연결 리스트의 순회에 대한 시간 복잡도는 O(n)입니다.

 

 

예제 2

• 링크드 리스트의 헤드가 주어졌을 때, 링크드 리스트에 사이클이 있는지 확인하세요.
• 링크드 리스트에 사이클이 있다는 것은 리스트의 어떤 노드를 시작으로 next 포인터를 계속 따라가면 다시 그 노드로 돌아올 수 있다는 것을 의미합니다.
• 내부적으로는 pos는 tail의 next 포인터가 연결된 노드의 인덱스를 나타내는 데 사용됩니다.
• 주의할 점은 pos가 파라미터로 전달되지 않는다는 것입니다.
• 링크드 리스트에 사이클이 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

 

예시 

• head = [3, 2, 0, -4], pos = 1
• 정답: true
• 링크드 리스트에 사이클이 잇으며, tail이 1번째 노드에 연결되어 있습니다.

 

방법

링크드 리스트에 사이클이 있는 경우, 일부 노드들이 원을 형성하며, 무한하게 순회하게 됩니다. 

브루트 포스 방법으로 풀이한다면, 리스트를 임의로 많은 횟수 동안 반복하는 것입니다. 사이클이 없다면 결국 리스트의 끝에 도달하겠져? 근데 사이클이 없지만, 반복 횟수보다 더 많은 노드가 있을 경우에는 틀리게 됩니다. 이런 하드 코딩은 나쁜 습관이에여.

 

더 나은 접근법은 Fast & Slow입니다. 사이클이 있는 경우, 속도가 빠른 주자는 결국 속도가 느린 주자를 따라잡게 됩니다.

첫 번째로 사이클을 한 바퀴 돌고나서 Fast 포인터가 한 위치 뒤에 있다면, 다음 반복에서는 Fast와 Slow 포인터가 만나게 됩니다. 만약 두 위치 뒤에 있다면, 다음 반복에서는 한 위치 뒤에 있게 되기 때문에 결국 두 포인터는 만나게 됩니다.

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var slow = head
        var fast = head

        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next

            if slow === fast {
                return true
            }
        }

        return false
    }
}

 

공간 복잡도는 O(1)이며, 리스트의 노드 수를 n이라고 할 때 시간복잡도는 O(n)입니다.

 

이를 해싱을 이용하여 풀이할 수 도 있습니다. 

아이디어는 다음과 같습니다.

1. 링크드 리스트에 사이클이 없는 경우, 결국 null에 도달하여 종료됩니다. -> false

2. 링크드 리스트에 사이클이 있는 경우, 결국 특정 노드를 두 번 방문하게 됩니다. -> true

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var seen: Set<ListNode> = []
        var current = head
        
        // 리스트를 순회
        while current != nil {
            // 현재 노드가 이미 집합에 있다면 사이클이 있는 것
            if seen.contains(current!) { return true }
            
            // 현재 노드를 집합에 추가
            seen.insert(current!)
            
            // 다음 노드로 이동
            current = current?.next
        }
        
        // 리스트의 끝에 도달하면 사이클이 없음
        return false
    }
}

 

O(n)의 공간복잡도를 가집니다.

이런 방법도 있지만, 링크드 리스트를 이용한 솔루션이 더 적은 공간을 사용하니 더 효율적입니다.

 

 

예제 3

• 링크드 리스트의 헤드 노드와 정수 k가 주어졌을 때, 끝에서 k번째 노드를 반환하세요.
• 예를 들어, 1 -> 2 -> 3 -> 4 -> 5를 나타내는 링크드 리스트와 k = 2가 주어지면, 끝에서 두 번째 노드인 값 4를 가진 노드를 반환합니다.

 

방법

두 개의 포인터를 사용하여 쉽게 해결할 수 있습니다.

두 포인터를 k만큼의 간격을 두고 분리한 다음, 같은 속도로 이동시키면 fast 포인터가 끝에 도달하면 slow 포인터는 끝에서 k번째 노드를 가리키고 있겠져?

func findNode(_ head: ListNode?, _ k: Int) -> ListNode? {
    var slow = head
    var fast = head
    
    // 빠른 포인터를 k만큼 이동
    for _ in 0 ..< k {
        fast = fast?.next
    }
    
    // 두 포인터를 같은 속도로 이동
    while fast != nil {
        slow = slow?.next
        fast = fast?.next
    }
    
    // 느린 포인터가 원하는 노드에 도달하면 반환
    return slow
}

 

첫 번째 예제와 같은 이유로, 공간 복잡도는 O(1), 시간 복잡도는 O(n)입니다.

 

 

 

Reference

- https://leetcode.com/