牛客网高频算法题系列-BM7-链表中环的入口结点

题目描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

原题目见：BM7 链表中环的入口结点

解法一：双指针法

使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

如果相遇了，从相遇处到入口结点的距离与头结点与入口结点的距离相同。所以将fast重新设置为头结点，fast和sow结点都一步步走，直到相遇，即为入口结点。

原理可参考：双指针算法原理详解

解法二：哈希法

使用HashSet记录链表中的结点，然后遍历链表结点：

  • 如果链表中的结点在哈希表中出现过，说明链表有环，并且该结点即为入口结点，返回之
  • 如果链表中的结点没有在哈希表中出现过，则将当前结点添加到哈希表中，然后判断下一个结点

最后，如果没有重复节点，则说明无环，返回null。

说明：和 牛客网高频算法题系列-BM6-判断链表中是否有环 的解法基本一致。

代码

  1. import java.util.HashSet;
  3. public class Bm007 {
  4.     /**
  5.      * 双指针
  6.      *
  7.      * @param pHead
  8.      * @return
  9.      */
  10.     public static ListNode entryNodeOfLoop(ListNode pHead) {
  11.         ListNode fast = pHead, slow = pHead;
  12.         while (fast != null && fast.next != null) {
  13.             // 快指针每次走2步，慢指针每次走1步
  14.             fast = fast.next.next;
  15.             slow = slow.next;
  16.             if (fast == slow) {
  17.                 // 快慢指针相遇，说明链表中有环
  18.                 break;
  19.             }
  20.         }
  21.         // 如果快指针为null，说明快慢指针没有相遇，无环，返回null
  22.         if (fast == null || fast.next == null) {
  23.             return null;
  24.         }
  26.         fast = pHead;
  27.         // 与第一次相遇的结点相同速度出发，相遇结点为入口结点
  28.         while (fast != slow) {
  29.             fast = fast.next;
  30.             slow = slow.next;
  31.         }
  33.         // 快慢指针没有相遇，说明无环
  34.         return fast;
  35.     }
  37.     /**
  38.      * 哈希法
  39.      *
  40.      * @param pHead
  41.      * @return
  42.      */
  43.     public static ListNode entryNodeOfLoop2(ListNode pHead) {
  44.         // 用来记录链表中的结点
  45.         HashSet<ListNode> nodes = new HashSet<>();
  46.         while (pHead != null) {
  47.             // 如果链表中的结点已经出现过，这个结点即为环的入口，返回之
  48.             if (nodes.contains(pHead)) {
  49.                 return pHead;
  50.             }
  51.             nodes.add(pHead);
  52.             pHead = pHead.next;
  53.         }
  54.         return null;
  55.     }
  57.     public static void main(String[] args) {
  58.         /**
  59.          * 测试用例链表结构为有环
  60.          * testCaseCycle：  3 -> 2 -> 0 -> -4
  61.          *                      ^          |
  62.          *                      ------------
  63.          */
  64.         ListNode head = ListNode.testCaseCycle();
  65.         /**
  66.          * 测试用例，期望输出： 2
  67.          */
  68.         System.out.println(entryNodeOfLoop(head));
  69.         System.out.println(entryNodeOfLoop2(head));
  70.     }
  71. }

牛客网高频算法题系列-BM7-链表中环的入口结点 - 图1
牛客网高频算法题系列-BM7-链表中环的入口结点 - 图2
相信坚持的力量！