单页网站开发费用,画册设计1p一般多少钱,重庆百科网站推广,东坑东莞微信网站建设我来更新 leetcode 题目了#xff0c;接着上一次#xff0c;这一次是上一道题目的提升#xff08;有点数学题的感觉#xff09; 142.环形链表2 题目 给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。 如果链表…我来更新 leetcode 题目了接着上一次这一次是上一道题目的提升有点数学题的感觉 142.环形链表2 题目 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 题目链接 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 文字 和 画图 分析 通过 141.环形链表 这里我们知道如何判断是否有环形链表并且同时可以得到当 fast指针 和 slow指针相遇时求出当时的相遇节点 这里先直接放出一个结论(meet指针 用来存放相遇节点 ,并且当fast指针 和 slow指针相遇时slow指针 回到 头节点head 的位置) meet指针 与 slow指针 指针同时走当两指针相遇时返回那个节点的位置(即为入环的第一个节点) 证明结论 假设 C 为链表的长度N 是当 slow指针 到达第一个入环的节点时与 fast指针 相距的距离 , X是当 fast指针 和 slow指针相遇时slow指针移动的距离 根据 fast指针 走的路程永远是 slow 走的路程的2倍可以推到出(n为12 , 3 ......) 2 *R X R n * C X R X n * C R n * C - X R (C - X) (n - 1) * C 这里为什么会有 n 呢主要是因为不知道当 slow指针 到达第一个入环的节点时 fast指针走了多少圈这与 R 和 C 有关 再者还有一点当 slow指针 到达第一个入环的节点时 ,fast指针追击 slow指针 一圈之内就可以结束因为它们之间的距离 N C , 每次缩小 1 走 N 步就追上了 代码
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *slow head;struct ListNode *fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){struct ListNode *meet slow;slow head;while(1){if(meet slow){return meet;}else{meet meet-next;slow slow-next;}}}}return NULL;
}
