微网站 无锡,广告制作费,企业网站建设 论文,wordpress安装教程 l题目#xff1a; 给定一个链表#xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。为了表示给定链表中的环#xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置#xff08;索引从 0 开始#xff09;。 如果 pos 是 -1#xff0c;…题目 给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 null。为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。 说明不允许修改给定的链表。
示例 1 输入head [3,2,0,-4], pos 1 输出tail connects to node index 1 解释链表中有一个环其尾部连接到第二个节点。 示例 2 输入head [1,2], pos 0 输出tail connects to node index 0 解释链表中有一个环其尾部连接到第一个节点。 示例 3 输入head [1], pos -1 输出no cycle 解释链表中没有环。
解题思路 看到这道题分两步去做我们首先要考虑的是这个链表有没有带环如果没有带环直接返回NULL就可以如果带环了就开始去找入口点 1、使用快慢指针来判断链表是否有环 如果这个链表没有尾节点pCur NULL那么这个节点就是带环的要怎么来判断呢如果是while(pCur)这样肯定不行如果这个链表带环就成了死循环所以要使用一对快慢指针来判断是否带环让快指针一次由两步慢指针一次走一步如果这个链表带环在一定的时间内这两个指针一定会相遇。 2、通过两个指针找带环链表的换入口节点 一个指针从快慢指针的相遇节点开始每次走一步零一个指针从链表的头节点开始每次走一步他们的相遇点就是入口节点为什么这两个指针的相遇节点就是入口节点呢下面用途来分析 结合上图开始推导 快指针在相遇前走的距离LXnR 慢指针在相遇前走的距离LX 所以2(LX) LXnR L nR-X n的最小值取1那么就是L R-X所以当这两个指针走的路是一样长那么他们相遇的节点就是入口节点。
代码解析 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {//先判断是否有环ListNode* pFast head;ListNode* pSlow head;while(pFast pFast-next){pFast pFast-next-next;pSlow pSlow-next;if(pFast pSlow)break;}if(pFast NULL || pSlow NULL)return NULL;//找入口节点else{ListNode* pCyc pFast;ListNode* pLine head;while(pCyc ! pLine){pCyc pCyc-next;pLine pLine-next;}return pCyc;}}
};
