无锡锡牛网站建设,移动网站和桌面网站区别,程序员做音乐网站,优秀app网站设计题目描述
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内…题目描述
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改 链表。
示例1
输入head [3,2,0,-4], pos 1
输出返回索引为 1 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例2
输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例3
输入head [1], pos -1
输出返回 null
解释链表中没有环。思路
使用快慢指针的策略。基本思想是使用两个指针一个快指针每次移动两步和一个慢指针每次移动一步。如果链表中存在环快指针最终会追上慢指针。当两个指针相遇时将一个指针重置到链表的头部然后两个指针都以相同的速度移动直到它们再次相遇这次相遇的节点就是环的起点。
算法流程 寻找相遇点 当 fast 和 slow 指针在链表中前进时如果链表存在环由于 fast 指针的速度是 slow 指针的两倍fast 会在某个时刻追上 slow在环内相遇。这是因为在环中快指针最终会从后面追上慢指针 如果 fast 指针遇到 nullptr表示链表尾部则链表中没有环函数返回 nullptr。 寻找环的起点 当 fast 和 slow 相遇时将其中一个指针例如 fast放回链表的起始位置 head然后 fast 和 slow 同时以相同的速度每步一节点前进 当 fast 和 slow 再次相遇时相遇点即为环的起点。这是因为从头节点到环入口的距离等于从相遇点到环入口的距离。
完整代码
#includeiostream
using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast head;ListNode *slow head;while(fast ! nullptr fast-next ! nullptr){fast fast-next-next;slow slow-next;if(fast slow){ListNode *index1 fast;ListNode *index2 head;while(index1 ! index2){index1 index1-next;index2 index2-next;} return index1;}} return nullptr;}
};int main()
{Solution s;ListNode *head new ListNode(0);ListNode *node1 new ListNode(1);ListNode *node2 new ListNode(2);ListNode *node3 new ListNode(3);head-next node1;node1-next node2;node2-next node3;node3-next node2;ListNode *cycleNode s.detectCycle(head);if (cycleNode) {cout The starting point value of the linked list is: cycleNode-val endl;} else {cout There is no ring in the linked list endl;}return 0;
}
