首頁猿問如何檢測鏈表中的循環(huán)？

如何檢測鏈表中的循環(huán)？

Java 算法算法與數(shù)據(jù)結(jié)構(gòu)

繁星點點滴滴 2019-07-27 14:51:40

如何檢測鏈表中的循環(huán)？假設(shè)您在Java中有一個鏈表結(jié)構(gòu)。它由節(jié)點組成：class Node { Node next; // some user data}每個節(jié)點都指向下一個節(jié)點，最后一個節(jié)點除外。假設(shè)列表有可能包含一個循環(huán) - 即最終的節(jié)點，而不是具有空值，具有對列表中之前的節(jié)點之一的引用。什么是最好的寫作方式boolean hasLoop(Node first)true如果給定的Node是帶循環(huán)的列表的第一個，它將返回，false否則？你怎么寫，這需要一個恒定的空間和合理的時間？

查看完整描述

3 回答

慕無忌1623718

TA貢獻1744條經(jīng)驗獲得超4個贊

您可以使用Floyd的循環(huán)尋找算法，也稱為烏龜和野兔算法。

我們的想法是對列表進行兩次引用，并以不同的速度移動它們。按1節(jié)點向前移動一個，按節(jié)點向前移動另一個2。

如果鏈表有一個循環(huán)，他們肯定會遇到。
否則兩個引用（或它們next）中的任何一個都將成為null。

實現(xiàn)該算法的Java函數(shù)：

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }}

反對回復(fù) 2019-07-27

泛舟湖上清波郎朗

TA貢獻1818條經(jīng)驗獲得超3個贊

以下是快速/慢速解決方案的改進，可正確處理奇數(shù)長度列表并提高清晰度。

boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops 

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates}

反對回復(fù) 2019-07-27

侃侃無極

TA貢獻2051條經(jīng)驗獲得超10個贊

對于Turtle和Rabbit的替代解決方案，并不像我暫時更改列表那樣好：

我們的想法是走在列表中，并在您前進時將其反轉(zhuǎn)。然后，當您第一次到達已經(jīng)訪問過的節(jié)點時，其下一個指針將指向“向后”，從而導(dǎo)致迭代first再次繼續(xù)，在此處終止。

Node prev = null;Node cur = first;while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;}boolean hasCycle = prev == first && first != null && first.next != null;// reconstruct the listcur = prev;prev = null;while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;}return hasCycle;

測試代碼：

static void assertSameOrder(Node[] nodes) {
    for (int i = 0; i < nodes.length - 1; i++) {
        assert nodes[i].next == nodes[i + 1];
    }}public static void main(String[] args) {
    Node[] nodes = new Node[100];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
    }
    for (int i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    Node first = nodes[0];
    Node max = nodes[nodes.length - 1];

    max.next = null;
    assert !hasCycle(first);
    assertSameOrder(nodes);
    max.next = first;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = max;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = nodes[50];
    assert hasCycle(first);
    assertSameOrder(nodes);}

反對回復(fù) 2019-07-27