快慢指针解决环型链表问题
链表中环的入口结点
http://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
因为快指针是慢指针的两倍速，且他们在p点相遇，则我们可以得到等式 2(A+B) = A+B+C+B
如果环前面的链表很长，而环短，那么快指针进入环以后可能转了好几圈(假设为n圈)才和慢指针相遇。但无论如何，慢指针在进入环的第一圈的时候就会和快的相遇。等式应更正为 2(A+B)= A+ nB + (n-1)C
因此可得 C = A。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode fast, slow;
boolean flag = false;
fast = pHead;
slow = pHead;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
//找到相遇点
if(slow == fast){
flag = true;
break;
}
}
//这里进行等式验证过，当slow == fast时就是环的入口
if(flag){
slow = pHead;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
return null;
}
}剑指Offer题解 文章被收录于专栏
为了之后反复练习方便查阅。
看到专升本+双非硕，我就知道，此事没那么简单