剑指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;   }};