LeetCode Entry

142. Linked List Cycle II

09.03.2023 medium 2023 kotlin

careful with corner cases.

142. Linked List Cycle II medium

blog post


fun detectCycle(head: ListNode?): ListNode? {
    var one = head
    var two = head
    do {
        one = one?.next
        two = two?.next?.next
    } while (two != null && one != two)
    if (two == null) return null
    one = head
    while (one != two) {
        one = one?.next
        two = two?.next
    }
    return one
}

Join me on telegram

https://t.me/leetcode_daily_unstoppable/143

Intuition

image.png There is a known algorithm to detect a cycle in a linked list. Move slow pointer one node at a time, and move fast pointer two nodes at a time. Eventually, if they meet, there is a cycle. To know the connection point of the cycle, you can also use two pointers: one from where pointers were met, another from the start, and move both of them one node at a time until they meet. How to derive this yourself?

  • you can draw the diagram
  • notice, when all the list is a cycle, nodes met at exactly where they are started
  • meet point = cycle length + tail

    Approach

  • careful with corner cases.

    Complexity

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)