链表中环的入口结点
题目描述
一个链表中包含环，请找出该链表的环的入口结点。
思路一：
用map或者set，遍历链表，把每一个节点映射到map中或者添加到set中，当要添加的节点在map或者set中已经存在的时候，就是我们要的入口节点了。这种方法的缺点就是牺牲了空间。
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead == NULL || pHead->next == NULL)
return NULL;
while(pHead != NULL){
m[pHead]++;
if(m[pHead] == 2)
return pHead;
pHead = pHead->next;
}
return NULL;
}
private:
map<ListNode*,int> m;
};
思路二：
快慢指针
/*解题思路：
时间复杂度为O（n）设置两个指针，开始都指向链表头，然后其中一个指针每次向前走一步，另一个指针每次向前走两步，如果快的遇到NULL了，证明该链表中没有环，如果有环，快的指针每次都要比慢的多走一步，最终两个指针会相遇。而相遇点p到入口点的距离=头指针到入口点的距离，因此，分别从相遇点、头指针开始走，相遇的那个位置就是环的入口结点。
*/
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead==null||pHead.next==null){
return null;
}
ListNode p1=pHead;
ListNode p2=pHead.next;
while(p2!=null){
p1.next=null;
p1=p2;
p2=p2.next;
}
return p1;
}
}
