给定一个有环链表，实现以算法返回环路的开头结点。 有环链表的定义 在链表中某个节点的next元素指向它前面出现过的节点，则表明该链表存在环路。 示例 输入：A-B-C-D-E-C(C节点出现两次) 输出：C 分析 ： 1，快慢指针法判断链表是否有环 fast每次前移两步，
给定一个有环链表，实现以算法返回环路的开头结点。
有环链表的定义
在链表中某个节点的next元素指向它前面出现过的节点，则表明该链表存在环路。
示例
输入：A->B->C->D->E->C(C节点出现两次)
输出：C
分析：
1，快慢指针法判断链表是否有环
fast每次前移两步，slow每次前移一步，两指针若能相遇，则有环，否则没有环。
2，假设链表头到环头移动k步，slow指向环头的时候，fast移动了2*k步，此时两者相距k步，也可以认为快指针再过m*size-k步之后追上慢指针。当两者相遇的时候，则慢指针距离环头还有k步。因为此时不知道k的具体大小，但是知道k是链表头到环头的步数，让fast指向链表头，之后快慢指针每次往后移动一步，两者相遇的地方就是环头。
package test;public class FindLoopStart { public Node findLoopStart(Node head){ Node fast = head; Node slow = head; while(fast!=null || fast.next!=null){ fast = fast.next.next; slow = slow.next; if(fast == slow) break; } //没有环则返回null if(fast==null || fast.next==null) return null; //相遇之后，slow节点再走k步达到环开头 //此时，并不知道k的具体值，但是知道k是从链表开头到环头的步数 //于是，让fast指向链表头，每次往后移一步，则<b>本文来源gao@dai!ma.com搞$代^码!网7</b>再次相遇的时候，走的步数就是k //则相遇地点就是环的开头 fast = head; while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; }}
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：CCI 2.6 寻找有环链表环路的开头节点
转载请注明原文链接：CCI 2.6 寻找有环链表环路的开头节点
