title: 链表中环的入口结点
date: 2023-07-25 11:57:00
tags:
- c/c++
categories:
- 算法
- 笔试
top:
链表中环的入口结点
题目来自acwing
题目(点击跳转)
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出null
。
数据范围
节点 val 值取值范围 [1,1000]。
节点 val 值各不相同。
链表长度 [0,500]。
样例
给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
思路:
双指针实现,定义两个指针,first和second,同时从链表头部开始走,first每次走一步,second每次走两步,当second遇到NULL时代表链表走到尽头,即没有环。当两个指针第一次相遇时,将first重置为头节点的位置,second位置不变,这时让两个指针都已每次一步的距离开始走,当两个指针再次相遇时,这个点就是环的入口。
证明:假设b点为环的起点,当first和second从a开始出发,当first走到b时,first走了距离x
,second走过了first两倍的路程,即为2x
,second可能在环上已经走过一圈以上,这次加入first再走y
距离与second相遇,那么second走的距离即为2y
,也就是说当first在b时,second与b的距离为y
,那当second走出了b点距离为y
时,在环上再走距离x
必定可以回到b点,那么将first从头节点开始走x
,此时与second第二次相遇即为环的开始节点。
代码:
/**
* 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;
auto first = head, 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;
}
};
标签:结点,中环,head,next,链表,second,节点,first
From: https://www.cnblogs.com/hhhhuaz/p/17579577.html