博文中会简要介绍Leetcode P0142题目分析及解题思路。
“Linked List Cycle II”这道题是p0141的变形题，这道题也是有两种思路，一种是双指针解法，第二种是用HashTable记录所有遍历过的结点，当出现环的时候一定是第二次访问环的头结点，所以可以得到头结点位置。上述第二种解法在C++中实现了，不过这篇博文会重点介绍第一种解法，即双指针解法，双指针解法同样也有两种思路。
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Notice that you should not modify the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
双指针解法的第一种思路比较简单直接。首先通过快慢指针确定有没有环，若有环则让快指针依次遍历环上结点得到环的长度len，最后快慢指针从头结点开始，快指针先走len长度的链表，接着快慢指针同时走，最终快慢指针相遇的时候，两个指针必定指向环的头结点。
以下是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) {
if (head == null)
return null;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null && fast != slow) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != slow)
return null;
// One more round to get the length of the cycle
int len = 1;
fast = fast.next;
while (fast != slow) {
fast = fast.next;
++len;
}
fast = head;
slow = head;
// fast pointer moves ahead for that length of the cycle
while (len > 0) {
fast = fast.next;
--len;
}
// Look for the beginning node of the cycle
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
双指针第二种解法没有那么直接，但是更加简单。以下是第二种Java的题解代码实现，需要计算长度之间的关系，利用如下等式关系来获得环的头指针。
令l1是链表总长，x是链表头指针到环的头指针的长度，l2是完成寻找后的slow/fast指针指向的位置与环的头指针的距离。则有，
l1+l2 = 2*(x+l2)
l1-x = 2*l2
x = l1-l2-x
发现右式其实就是当前fast指针到环的头指针的距离-1
/**
* 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)
return null;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null && fast != slow) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != slow)
return null;
ListNode dummy = new ListNode(0, head);
slow = dummy;
// Look for the beginning node of the cycle
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> node_set;
ListNode *curr = head;
while (curr != nullptr) {
if (node_set.count(curr) > 0)
return curr;
node_set.insert(curr);
curr = curr->next;
}
return nullptr;
}
};