Linked List Cycle II

今天是一道有关链表的题目，是Linked List Cycle（回复022查看）的升级版，来自LeetCode，难度为Medium，Acceptance为31.4%。

题目如下

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?

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

首先，该题是Linked List Cycle（回复022查看）的升级版。在Linked List Cycle一题中，只需要求是否有环，比较容易。 只需用两个指针，一快一慢，快指针一次走两步，慢指针一次走一步。

• 若快指针最后指向null，则无环；
• 若快慢指针最后相遇则有环。

然后，在该题中要进一步求链表开始的节点。这里需要一点数学计算，如图所示：

链表计算.png

• 首先，设从链表头到环开始节点距离为x；环的长度为y；从环开始处到相遇处距离为k；x即为我们要求的距离。
• 第一步，设快指针与慢指针在5节点处相遇，则快指针走过x+y+k；慢指针走过x+k。因为我们已知快指针走过的长度为慢指针的两倍，则可得公式1 2(x + k) = x + y + k；
• 第二步，整理公式，得到公式2 x + k = y；
• 第三步，得到公式3 x = y - k即为我们要求的距离。

有了上面的计算过程，下面我们就可以按照以下思路求该节点。

• 即当快慢指针相遇时，我们从链表头节点再定义一个指针，每次一步向前移动，同时慢指针继续每次一步的移动。
• 当该指针移动了x步时，慢指针此时也移动了x步；
• 而我们已由公式3可知x = y - k，即此时新的节点移动到了4节点，慢指针也到了4节点，两个指针在此处相遇。次节点即为我们要求的节点。

最后，我们来看代码。

代码如下

Java版

/**
 * 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){
                ListNode slow2 = head;
                while(slow2 != slow){
                    slow2 = slow2.next;
                    slow = slow.next;
                }
                return slow2;
            }
        }
        return null;
    }
}

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image