剑指office（Java版）|面试题22（链表中环的入口节点（Java版））

2022-05-14 java 数据结构链表

【剑指office（Java版）|面试题22（链表中环的入口节点（Java版））】题目：如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。例如，在如图4.3所示的链表中，环的入口节点是节点 3。

题目分析
因为要找到环的入口节点，所以首先需要判断链表是否有环，当链表有
环时，我们可以使用两个指针（一个快指针和一个慢指针），快指针一
次移动两下，慢指针一次移动一下，当两个指针相遇时则表明此时两个
指针已经进入到环里了，且设快指针移动了2k步，则慢指针移动了k步，
仔细观察可以发现当慢指针再移动k步会回到原地（因为2k步的位置和
k步相同），即移动k步相当于移动了整数圈环（所以k为环中节点的整
数倍）。所以我们可以将一个指针p2指向那个移动了k步的慢指针再将
一个指针p1指向链表的表头，两个指针再同时移动，当p1移动到环的
入口时，因为指针p2始终比指针p1快k步，又因为k为环中节点的整数
倍，所以指针p2也指向了环的入口节点即当p1与p2相遇的时候，指向
的节点就为环的入口节点。
实际实现

// 获取链表中两个快慢指针相遇的位置， // 即两个指针在环中相遇的位置 private ListNode getNodeInLoop(ListNode head) { // 当节点少于两个时无法形成环，所以返回null if (head == null || head.next == null) { return null; } // 初始化快指针和慢指针的位置 ListNode slow = head.next; ListNode fast = slow.next; // 当快指针不为null时，则同时移动快慢指针 // （快指针移动两格，慢指针移动一格） // 如果循环过程中出现fast为null的话则 // 证明链表中不存在环返回null while (fast != null) { // 如果slow和fast相等，返回 // 两个指针相遇的位置 if (slow == fast) { return slow; } slow = slow.next; fast = fast.next; if (fast != null) { fast = fast.next; } } return null; }public ListNode detectCycle(ListNode head) { ListNode inLoop = getNodeInLoop(head); // 如果链表中不存在环则返回null if (inLoop == null) { return null; }// 初始化node为头结点 ListNode node = head; // 当node != inLoop时node和inLoop同时移动 // 当node与inLoop相等时说明已经到环的入口点了 while (node != inLoop) { node = node.next; inLoop = inLoop.next; } return node; }

推荐阅读

上一篇：Python|第十二届青少年蓝桥杯 Python 组3月中/高级试题

下一篇：前端|vue社区之---前端面试（前端中的那些方法）