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?

头结点到cycle begins的点距离是A, cycle begins的点到快慢结点相遇的点的距离是B

A+B+N = 2*(A+B)

A+B = N

所以快慢指针相遇后，从头结点开始再跑一个慢指针，直到2个慢的相遇，相遇的点就是cycle begin

 1 public class Solution {
 2     public ListNode detectCycle(ListNode head) {
 3         ListNode faster = head;
 4         ListNode slower = head;
 5         
 6         while(faster !=null && faster.next != null){
 7             faster = faster.next.next;
 8             slower = slower.next;
 9         
10             if(faster == slower){
11                 ListNode slower2 = head;
12                 while(slower != slower2){
13                     slower = slower.next;
14                     slower2 = slower2.next;
15                 }
16                 return slower;
17             }
18        }
19        return null;
20         
21     }
22 }

142. Linked List Cycle II（找出链表相交的节点）

相关推荐