每日算法题 19---142.环形链表Ⅱ

引言在这个系列里面也讲过一道环形链表题那道题是判断一个链表是否是环形链表而这道题是找出环形链表的入口题目142.环形链表Ⅱ要求给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。示例思路在判断是否为环形链表时用到了快慢指针的原理这道题依旧使用快慢指针先来判断是否为环形链表判断是环形链表之后就来找入口找入口的原理用到了数学知识假设链表有ab个节点链表头部到链表入口有 a 个节点链表环有 b 个节点设快指针走了 f 步慢指针走了 s 步快指针走的是慢指针的两倍快慢指针的速度比f2s快指针比慢指针多走了 n 个环的长度相遇的地方一定是链表环里的某个节点因此多走了n个环的长度fsnb将这两个式子整合得到snb这意味着从开始到相遇快慢指针分别走了2n、n个链表环上述相遇过程理解清楚后我们就来构造第二次相遇使相遇的地点刚好是链表环的入口令fast指针重新指向链表的头节点此时 f0snb快慢指针现在同时向前走一步当fast指针走了 a 步后slow指针走了 anb步此时两指针相遇同时站在了链表环的入口处为什么说一定是入口呢因为走 anb 步 即先走 a 步到入口节点之后每绕 1 圈环 b 步都会再次到入口节点代码/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode fasthead; ListNode slowhead; while(true){ if(fastnull || fast.nextnull){ return null; } fastfast.next.next; slowslow.next; if(fastslow) break; } fasthead; while(slow!fast){ slowslow.next; fastfast.next; } return fast; } }