首页 > 代码库 > Linked List Cycle II <leetcode>
Linked List Cycle II <leetcode>
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?
算法：该题大意是求一个链表中是不是有环，如果没有环，返回NULL，如果存在环，返回环开始的节点
这个题是个纯数学题，在网上查了一些资料才解决，方法：设置一个快指针--fast，一个慢指针--slow，slow每次向下走一步，fast每次向下走两步，如果有环，这两个指针必定会在环中相遇，假设，环开始的节点距离头节点的步数是m，换的大小是n步，第一次在环中相遇的地方距离环开始的地方步数是x，那么 slow 走了m+x步，fast走了2m+2x步，fast在环中走的步数是m+2x，所以（m+2x）%n=x; ==》m+2x=k*n+x;==>m+x=k*n;(k=1,2,3...)==>第一次相遇后，把其中一个指针放到头节点，并把他们的速度都调节为1步；这样的话，再走m步，该指针能到环开始的节点，而仍然在环中的指针再走m步，也会到环开始的节点，<m+x=k*n;(k=1,2,3...)>此时他们相遇，就可以确定环开始的节点。。:代码如下：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *detectCycle(ListNode *head) {12 if(NULL==head) return NULL;13 ListNode *fast=head;14 ListNode *slow=head;15 while(NULL!=fast)16 {17 slow=slow->next;18 fast=fast->next;19 if(NULL==fast) return NULL;20 fast=fast->next;21 if(slow==fast&&NULL!=fast)22 {23 slow=head;24 while(slow!=fast)25 {26 slow=slow->next;27 fast=fast->next;28 }29 return fast;30 }31 32 }33 return NULL;34 }35 };
Linked List Cycle II <leetcode>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。