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?

Approach:

The difficulty of this problem lies in returning to the cycle begins. We previously used fast and slow pointers to determine if a cycle had occurred, but how do we return to the initial point? I found a relatively easy-to-understand explanation online:

When fast and slow meet at point p, the length they have run are ‘a+2b+c’ and ‘a+b’.
Since the fast is 2 times faster than the slow. So a+2b+c == 2(a+b), then we get ‘a==c’.

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