首页 > 代码库 > LeetCode OJ - Linked List Cycle II

LeetCode OJ - Linked List Cycle II

题目:  

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

  Follow up:

  Can you solve it without using extra space?

解题思路:

  设置两个指针slow和fast,从head开始,slow一次一步,fast一次两步,如果fast能再次追上slow则有圈。

  设slow走了n步,则fast走了2*n步,设圈长度m,圈起点到head距离为k,相遇位置距离圈起点为t,则有:

  n = k + t + pm; (1)

  2*n = k + t + qm;(2)

  这里p和q是任意整数。(不过fast速度是slow二倍,则肯定在一圈内追上,p就是0了)

  2 * (1) - (2) 得k = lm - t;(l = q - 2 * p)

   即 k 的长度是若干圈少了 t 的长度。

  因此这时候,一个指针从head开始,另一个从相遇位置开始,都每次只走一步,当从head开始的指针走到圈开始位置时,两指针刚好相遇。

代码如下:

  

/**
 * 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) {
        if (head == null || head.next == null) return null;
        ListNode fast = head, slow = head;
        
        do {
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            } else {
                return null;
            }
            if (fast == null) return null;
            slow = slow.next;
        }while (fast != slow);
        
        ListNode behind = head, front = slow;
        while (behind != front) {
            behind = behind.next;
            front = front.next;
        }
        return behind;
    }
}