剑指offer 55链表中环的入口结点

题目描述

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

第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
  
第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x;
    n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2;
    此时p1指向环的入口。

/*
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||pHead->next->next==NULL){
            return NULL;
        }
        
        ListNode* fast=pHead->next->next;
        ListNode* slow=pHead->next;
       
        while(fast!=slow){
            if(fast->next!=nullptr&&fast->next->next!=nullptr){
                fast=fast->next->next;
                slow=slow->next;
            }else{
                return nullptr;
            }
        }
       
        fast=pHead;
        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        
        return slow;
    }
};

s.insert(node).second   解释如下：
set的带有一个键参数的insert版本函数返回pair类型对象，该对象包含一个迭代器和一个bool值，迭代器指向拥有该键的元素，而bool值表明是否添加了元素。
这里的second即是返回的pair里的bool值。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        set<ListNode*> s;
        ListNode* node = pHead;
        while(node!=NULL){
            if(s.insert(node).second)
                node = node->next;
            else
                return node;
        }
        return node;
         
    }
};

使用map
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    map<ListNode*, int> temp;
	ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
		if (pHead == NULL || pHead->next == NULL){
            return NULL; 
        }
  		ListNode* pNode = pHead; 
 		while ((temp[pNode]++) < 2) {
             pNode = pNode->next; 
         }
  		return pNode; 

  }
};