【剑指offer】链表中环的入口结点（链表）

本文主要是介绍【剑指offer】链表中环的入口结点（链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

链接

https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路

第一种解法：
用一个set集合保存访问到的每一个指针，然后对整个链表依次进行访问，如果访问到NULL都没有遇到相同的指针，则该链表无环。如果某个时刻访问到的指针曾经出现过，则该指针就是环的入口。

第二种解法：
1、用1快1慢的两个指针对链表进行访问，慢的指针每次前进1个，快的指针每次前进2个。如果快的指针某个时刻指向NULL，则证明无环，如果某个时刻快的指针追上慢的指针，则证明有环。且相遇时的指针一定位于环中。
2、在有环的情况下，从相遇的指针处开始遍历访问，并计数，当指针再次为相遇时的指针时，计数的值便是环的大小。
3、得到了环的大小num，就可以让一前一后两个指针相隔num，然后两个指针同步向前，某个时刻两个指针必将指向相同的节点，即为入口点。

代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/// 第一种解法
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead){if(pHead == NULL){return NULL;} set<ListNode*> ss;while(pHead){if(ss.find(pHead) == ss.end()){ss.insert(pHead);}else{return pHead;}pHead = pHead->next;}return NULL;}
};
// 第二种解法
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead){ListNode* meetingNode = MeetingNode(pHead);if(meetingNode == NULL){return NULL;}// 获取环中的节点数int num = 1;ListNode* temp = meetingNode->next;while(temp != meetingNode){num++;temp = temp->next;}// 让两个指针相差num去寻找入口ListNode* pNode1 = pHead;ListNode* pNode2 = pHead;while(num--){pNode1 = pNode1->next;} while(pNode1 != pNode2){pNode1 = pNode1->next;pNode2 = pNode2->next;}return pNode1;}ListNode* MeetingNode(ListNode* pHead){if(pHead == NULL){return NULL;}ListNode* first = pHead->next;if(first == NULL){return NULL;}ListNode* second = first->next;while(second != NULL && first != NULL){if(first == second){return first;}first = first->next;second = second->next;if(second != NULL){second = second->next;}}return NULL;}
};