题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
解题思路
这个题包含两个子问题，一个是判断链表是否有环，另一个是如果有环，找到环的入口。
对于如何判断链表有环问题，较为基础：快慢指针。
-
对于如何找到环的入口，这个地方需要推导一下：
x表示头结点到入口结点的距离，表示入口结点到fast和slow相遇结点的距离，z是环中剩下的长度，即有z+y=L。L表示的是环的长度。那么当快慢指针相遇时候有：S = x+y 2*S = x+y+nL。即，慢指针走过x+y的结点，快指针比慢指针多走了n圈。这里慢指针在环中也可能多走了几圈才相遇的，但是可以不用表示出来。因为快指针的nL表示的就是比慢指针多走的圈数。举例：慢指针如果走 x+y+2L，快指针走 x+y+4L 那么就可以写成：慢x+y 快x+y+2L.是等价的。
消去s，可得，同时：
，代入消去y，可得
如图
得到 能说明什么问题呢？
走x步，等于走 n-1圈再走上z步。走x步，正好就是从头结点到环入口结点。而z步是从相遇地方，到入口结点，在加上多少圈，实际走的都是从相遇到入口结点。举个例子，如果n = 1，那么x=z。如果n=2，那么x=L+z.就是多走一圈到相遇结点，然后再走z步还是到环的入口结点。
这个时候，我们只需要令一个结点从头结点出发，走x步，另一个结点从相遇结点出发，走n圈（n=0,1,2,...）再走z步，他们会同时到达环的入口地方。
题解
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead == null) return null;
if (isLoop(pHead)){
ListNode slow = pHead.next;
ListNode fast = pHead.next.next;
while(slow != fast){
slow = slow.next;
fast = fast.next.next;
}
// 循环结束时候 slow == fast
slow = pHead;
// 一个从头开始走 ，一个从相遇地方开始走，走同样的步数
// 因为 x= z+(n-1)L
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
else return null;
}
public boolean isLoop(ListNode pHead){
if (pHead.next == null) return false;
ListNode slow = pHead;
ListNode fast = pHead;
while (fast != null && fast.next !=null){
slow = slow.next;
fast = fast.next.next;
if (slow == fast){
return true;
}
}
return false;
}
