ACWING34. 链表中环的入口结点（剑指offer）

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

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

样例

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

思路：
很巧妙的思路，暴力思路是直接开一个vis数组或者map之类判重。省空间的写法是，用两个指针，一个一次走一步，一个一次走两步。当相遇的时候，第一个指针退回到起点，然后每一个指针各走一步直到相遇，再次相遇点就是入口。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* entryNodeOfLoop(ListNode* head) {if(!head || !head -> next) return NULL;ListNode* first = head;ListNode* second = head;while(first && second) {first = first -> next;second = second -> next;if(second) second = second -> next;else return NULL;if(first == second) {first = head;while(first != second) {first = first -> next;second = second -> next;}return first;}}return NULL;}
};

这篇关于ACWING34. 链表中环的入口结点（剑指offer）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---