链表-链表中环的入口结点-java/c++

链表中环的入口结点

题目描述

一个链表中包含环，请找出该链表的环的入口结点。

思路一：

用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;
    }
}