[LeetCode] 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Thought process:

The trick is:

1. Start with two pointers as in "141. Linked List Cycle".
2. After fast and slow collide in the cycle, pull either one back to head, and increment both pointers by one node in each iteration. The node where they collide again is where the cycle begins. There's no need to understand how to prove this.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next!= null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } if (fast == null || fast.next == null) { return null; } fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }

Time complexity:

The overall time complexity will be no more than two iterations of the list. O(n).