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

5次阅读

共计 1498 个字符,预计需要花费 4 分钟才能阅读完成。

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

题目形容

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

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

解法一:双指针法

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

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

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

解法二:哈希法

应用 HashSet 记录链表中的结点,而后遍历链表结点:

  • 如果链表中的结点在哈希表中呈现过,阐明链表有环,并且该结点即为入口结点,返回之
  • 如果链表中的结点没有在哈希表中呈现过,则将以后结点增加到哈希表中,而后判断下一个结点

最初,如果没有反复节点,则阐明无环,返回 null。

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

代码

import java.util.HashSet;

public class Bm007 {
    /**
     * 双指针
     *
     * @param pHead
     * @return
     */
    public static ListNode entryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead, slow = pHead;
        while (fast != null && fast.next != null) {
            // 快指针每次走 2 步,慢指针每次走 1 步
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 快慢指针相遇,阐明链表中有环
                break;
            }
        }
        // 如果快指针为 null,阐明快慢指针没有相遇,无环,返回 null
        if (fast == null || fast.next == null) {return null;}

        fast = pHead;
        // 与第一次相遇的结点雷同速度登程,相遇结点为入口结点
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        // 快慢指针没有相遇,阐明无环
        return fast;
    }

    /**
     * 哈希法
     *
     * @param pHead
     * @return
     */
    public static ListNode entryNodeOfLoop2(ListNode pHead) {
        // 用来记录链表中的结点
        HashSet<ListNode> nodes = new HashSet<>();
        while (pHead != null) {
            // 如果链表中的结点曾经呈现过,这个结点即为环的入口,返回之
            if (nodes.contains(pHead)) {return pHead;}
            nodes.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }

    public static void main(String[] args) {
        /**
         * 测试用例链表构造为有环
         * testCaseCycle:3 -> 2 -> 0 -> -4
         *                      ^          |
         *                      ------------
         */
        ListNode head = ListNode.testCaseCycle();
        /**
         * 测试用例,冀望输入:2
         */
        System.out.println(entryNodeOfLoop(head));
        System.out.println(entryNodeOfLoop2(head));
    }
}

$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量!

正文完
 0