首页 > 代码库 > Linked List Cycle II
Linked List Cycle II
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
比I麻烦点的就是找到循环开始点TAT
I只是判断是否循环。要求不使用额外空间（不然hash就可以了
按I的思路，我们又慢指针S和快指针F。。。F走两步，S走一步。。。若有环，必定相遇。
假设在红色凸起的地方相遇了。
F走的路程应该是S的两倍
S = x + y
F = x + y + z + y = x + 2y + z
2*S = F
2x+2y = x + 2y + z
得到x = z
也就是从head到环开始的路程 ＝ 从相遇到环开始的路程
那么。。。只要S和F相遇了，我们拿一个从头开始走，一个从相遇的地方开始走
两个都走一步，那么再次相遇必定是环的开始节点！
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 == NULL) return NULL; ListNode* S = head; ListNode* F = head; while(F != NULL) { if(F) F = F->next; if(F) F = F->next; if(S) S = S->next; if(F != NULL && F == S){ S = head; while(S != F) { F = F->next; S = S->next; } return S; } } return NULL; }};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 slow = head; ListNode fast = head; while(true){ if(fast == null || fast.next == null){ return null; } slow = slow.next; fast = fast.next.next; if(slow == fast) break; } slow = head; while(slow != fast){ slow = slow.next; fast = fast.next; } return slow; }}
Linked List Cycle II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。