[Algorithm] LeetCode - Linked List Cycle

📠 문제

• Linked List Cycle
• 난이도: Easy
• 연결리스트 사이클이 있는지 찾는 문제

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

💡 풀이

솔직히 이 문제가 왜 Easy인지 모르겠다. 아래처럼 ListNode 배열이나 ObjectIdentifier 집합을 사용하여 풀면 풀리긴 하지만... 이런 문제를 풀 때 아주아주 유명한 알고리즘이 있다.

func hasCycle(_ head: ListNode?) -> Bool {
    var visited: [ListNode] = []
    var current = head

    while let node = current {
        if visited.contains(where: { $0 === node }) { return true }
        visited.append(node)
        current = node.next
    }

    return false
}

func hasCycle(_ head: ListNode?) -> Bool {
    var visited = Set<ObjectIdentifier>()
    var current = head

    while let node = current {
        let id = ObjectIdentifier(node)
        if visited.contains(id) {
            return true
        }
        visited.insert(id)
        current = node.next
    }

    return false
}

바로 아래처럼 플로이드의 토끼와 거북이 알고리즘을 사용하면 저장하는것이 없기 때문에 훨씬 효율적으로 풀 수 있다. 거북이는 한 칸 이동, 토끼는 두 칸 이동! 사이클의 개수는 홀수 혹은 짝수이기 때문에 언젠간 만난다.

func hasCycle(_ head: ListNode?) -> Bool {
    var 🐢 = head
    var 🐇 = head

    while let next = 🐇?.next?.next {
        🐢 = 🐢?.next
        🐇 = next

        if 🐢 === 🐇 { return true }
    }

    return false
}

 

아래와 같이 문제와 관련된 유튜버 Joma Tech님의 재미있는 영상도 있다.