假设您在Java中有一个链表结构。它由节点组成:

class Node {
    Node next;
    // some user data
}

每个节点都指向下一个节点,除了最后一个节点,它的next为空。假设有一种可能性,列表可以包含一个循环-即最后的节点,而不是有一个空值,有一个引用到列表中它之前的一个节点。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是带有循环的列表的第一个,则返回true,否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?

下面是一个带有循环的列表的图片:


当前回答

我读了一些答案,人们忽略了上述问题的一个明显的解决方案。

如果给定我们可以改变类Node的结构,那么我们可以添加一个布尔标志来知道它是否被访问过。这样我们只遍历列表一次。

Class Node{

 Data data;
 Node next;
 boolean isVisited;

}


public boolean hasLoop(Node head){
   
     if(head == null) return false;

     Node current = head;


     while(current != null){
      if(current.isVisited) return true;
      current.isVisited = true;
      current = current.next;
     }

    return false;

}

其他回答

算法

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

复杂性

Time ~ O(n)
Space ~ O(n)

乌龟和兔子

看看波拉德的算法。这不是完全相同的问题,但也许你会理解其中的逻辑,并将其应用于链表。

(如果你很懒,你可以看看周期检测——看看关于乌龟和兔子的那部分。)

这只需要线性时间和2个额外的指针。

在Java中:

boolean hasLoop( Node first ) {
    if ( first == null ) return false;

    Node turtle = first;
    Node hare = first;

    while ( hare.next != null && hare.next.next != null ) {
         turtle = turtle.next;
         hare = hare.next.next;

         if ( turtle == hare ) return true;
    }

    return false;
}

(大多数解决方案不会同时检查next和next。接下来是null。此外,因为乌龟总是在后面,你不需要检查它是否为空——兔子已经检查过了。)

用户unicornaddict上面有一个很好的算法,但不幸的是,它包含一个错误,用于奇数长度>= 3的非循环列表。问题是,快的可能会在列表结束之前“卡住”,慢的会赶上它,然后就会(错误地)检测到循环。

这是修正后的算法。

static 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 = null;
        else
            fast = fast.next.next; // 2 hops.

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

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

这是我的可运行代码。

我所做的是通过使用三个临时节点(空间复杂度O(1))来对链表进行尊崇,以跟踪链接。

有趣的是,这样做有助于检测链表中的循环,因为当你向前移动时,你不期望回到起点(根节点),其中一个临时节点应该为null,除非你有一个循环,这意味着它指向根节点。

该算法的时间复杂度为O(n),空间复杂度为O(1)。

下面是链表的类节点:

public class LinkedNode{
    public LinkedNode next;
}

下面是带有三个节点的简单测试用例的主要代码,最后一个节点指向第二个节点:

    public static boolean checkLoopInLinkedList(LinkedNode root){

        if (root == null || root.next == null) return false;

        LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
        root.next = null;
        current2.next = current1;

        while(current3 != null){
            if(current3 == root) return true;

            current1 = current2;
            current2 = current3;
            current3 = current3.next;

            current2.next = current1;
        }
        return false;
    }

下面是一个简单的三个节点的测试用例,最后一个节点指向第二个节点:

public class questions{
    public static void main(String [] args){

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        LinkedNode n3 = new LinkedNode();
        n1.next = n2;
        n2.next = n3;
        n3.next = n2;

        System.out.print(checkLoopInLinkedList(n1));
    }
}

这段代码经过优化,将比选择的最佳答案更快地产生结果。这段代码避免了进入一个非常长的追逐向前和向后节点指针的过程,如果我们遵循'最佳答案'方法,在以下情况下将发生这种情况。看一下下面的演练,你就会明白我想说的是什么。然后通过下面给出的方法来观察问题,并测量否。为了找到答案所采取的步骤。

1 - > 2 - > 9 - > 3 ^ -- -- -- -- -- -- -- - ^

代码如下:

boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}