Daily LeetCode Challenge - 142. Linked List Cycle II

Problem From.
https://leetcode.com/problems/linked-list-cycle-ii/

오늘 문제는 Linked list 에서 linked list 가 순회하기 시작하는 곳의 인덱스를 구하는 문제였다.

이 문제는 two 포인터를 응용하여 풀 수 있는데,
첫번째 느린 포인터는 하나씩 탐색하며 진행하고,
그 다음 빠른 포인터는 한번에 두개씩 탐색하며 진행한다.
그렇게 한번에 두개씩 차이를 내가다가 첫번재 포인터와 두번째 포인터의 값이 같아지는 부분이 존재하면, 사이클이 존재하는 것이므로, 첫번째 포인터의 값을 반환한다.

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */

class Solution {
  fun detectCycle(root: ListNode?): ListNode? {
    val point: ListNode? = ListNode(-1)
    point!!.next = root
    var fast = point
    var slow = point

    while (true) {
      if (fast?.next == null) return null

      fast = fast.next!!.next
      slow = slow!!.next

      if (fast == slow) break
    }

    slow = point
    while (fast != slow) {
      fast = fast!!.next
      slow = slow!!.next
    }
    return slow
  }
}