Leetcode: Linked List Cycle II
Leetcode: Linked List Cycle II
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 15:54:41
发布于 2019-01-22 15:54:41
题目： Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
思路分析： 和《Leetcode: Linked List Cycle 》一样还是双指针的方法。
循环链表
一个循环链表如图 slow指针走了S=X+Y fast指针走了F=X+Y+Z+Y 两个指针相遇。 且有：2S=F，则有X=Z。 所以，从head到环开始的路程 ＝ 从相遇到环开始的路程。 所以，当slow和fast相遇了，我们拿slow从头开始走，fast从相遇的地方开始走，两个都走一步，那么再次相遇必定是环的开始节点。
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)
{
if (!head) return nullptr;
ListNode *slow = head;
ListNode *fast = head;
bool hasCycle = false;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
hasCycle = true;
break;
}
}
if (hasCycle)
{
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
else return nullptr;
}
};C#参考代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution
{
public ListNode DetectCycle(ListNode head)
{
if (head == null) return null;
ListNode slow = head;
ListNode fast = head;
bool hasCycle = false;
while (fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
{
hasCycle = true;
break;
}
}
if (hasCycle)
{
slow = head;
while (slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return slow;
}
else return null;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年04月05日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读