面试算法22：链表中环的入口节点（2）

本文主要是介绍面试算法22：链表中环的入口节点（2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。

例如，在如图4.3所示的链表中，环的入口节点是节点3。
在这里插入图片描述

分析

第1步：确认是否包含环

定义两个指针并同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果链表中不包含环，走得快的指针直到抵达链表的尾节点都不会和走得慢的指针相遇。如果链表中包含环，走得快的指针在环里绕了一圈之后将会追上走得慢的指针。因此，可以根据一快一慢两个指针是否能够相遇来判断链表中是否包含环。

第2步：如何找到环的入口节点

上述代码需要求出链表的环中节点的数目。如果仔细分析，就会发现其实并没有必要求得环中节点的数目。如果链表中有环，快慢两个指针一定会在环中的某个节点相遇。慢的指针一次走一步，假设在相遇时慢的指针一共走了k步。由于快的指针一次走两步，因此在相遇时快的指针一共走了2k步。因此，到相遇时快的指针比慢的指针多走了k步。另外，两个指针相遇时快的指针比慢的指针在环中多转了若干圈。也就是说，两个指针相遇时快的指针多走的步数k一定是环中节点的数目的整数倍，此时慢的指针走过的步数k也是环中节点数的整数倍。
此时可以让一个指针指向相遇的节点，该指针的位置是之前慢的指针走了k步到达的位置。接着让另一个指针指向链表的头节点，然后两个指针以相同的速度一起朝着指向下一个节点的指针移动，当后面的指针到达环的入口节点时，前面的指针比它多走了k步，而k是环中节点的数目的整数倍，相当于前面的指针在环中转了k圈后也到达环的入口节点，两个指针正好相遇。也就是说，两个指针相遇的节点正好是环的入口节点。
在这里插入图片描述

解

public class Test {public static void main(String[] args) {ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;listNode5.next = listNode6;listNode6.next = listNode3;ListNode result = detectCycle(listNode1);System.out.println(result.val);}public static ListNode detectCycle(ListNode head) {ListNode inLoop = getNodeInLoop(head);if (inLoop == null) {return null;}ListNode node = head;while (node != inLoop) {node = node.next;inLoop = inLoop.next;}return node;}// 快慢指针找到相遇的节点private static ListNode getNodeInLoop(ListNode head) {if (head == null || head.next == null) {return null;}ListNode slow = head.next;ListNode fast = slow.next;while (slow != null && fast != null) {if (slow == fast)return slow;slow = slow.next;fast = fast.next;if (fast != null)fast = fast.next;}return null;}
}