『剣指offer』チェーンテーブルのリングの入口ノード

1617 ワード

剣指offer-java Linked List チェーンテーブル面接問題学校募集の准备

注意:このブログは更新されません.すべての最新記事は個人独立ブログlimengtingに発表されます.site.技術を共有し、生活を記録し、注目を集めてください.
タイトルはチェーンテーブルにリングが含まれていることを説明します.チェーンテーブルのリングの入口ノードを見つけてください.方法一:空間複雑度O(n)

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.HashSet;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        // 1、head key hashset， key， value， O(n)
        if (pHead == null) return null;
        HashSet set = new HashSet<>();
        while (pHead != null) {
            if (!set.add(pHead)) {
                return pHead;
            }
            pHead = pHead.next;
        }
        return null;
    }
}

方法2:空間複雑度O(1)

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        // 2、 
        //  ， ， 
        //  ， ， ， 
            if (pHead == null || pHead.next == null) return null;
            ListNode fast = pHead.next.next;
            ListNode slow = pHead.next;
            while (fast != slow) {
                if (fast == null || fast.next == null) {
                    return null;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            fast = pHead;
            while (fast != slow) {
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
    }
}

[プログラマー]Kaka friends彩本

プログラマ-機能開発