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

LeetCode OJ - Linked List Cycle II

2024-07-04 09:01:38   223人阅读

题目：　　

　　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;
    }
}

 


联系
我们