题解 | #链表中环的入口结点#
链表中环的入口结点
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
ListNode* fast = pHead, *slow = pHead;
// 1. 找到相遇点
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
// 2.没到找相遇点，就返回nullptr
if (fast == nullptr || fast->next == nullptr) return nullptr;
// 快指针走x + n(y+z) + y 慢指针走 x + m(y+z) + y
// x+y = (n-2m)(y+z) 即，链表头到相遇位置的距离是环距离的整数倍
// 那么一个指针从链表头开始 另一个从相遇位置开始 会同时走到相遇位置，而在走到相遇位置前，都会同一时刻经过环的入口节点
ListNode* res = pHead;
while (res != slow) {
res = res->next;
slow = slow->next;
}
return res;
}
};
投递阿里巴巴灵犀互娱等公司10个岗位 >
查看7道真题和解析
