如何检测链表中的循环?

小开

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

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

这只需要线性时间和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.next是否为空。此外，因为乌龟总是在后面，你不需要检查它是否为空——兔子已经检查过了。)

小开

下面的方法可能不是最好的——它是O(n²)。然而，它应该有助于完成工作(最终)。

count_of_elements_so_far = 0;
for (each element in linked list)
{
search for current element in first <count_of_elements_so_far>
if found, then you have a loop
else,count_of_elements_so_far++;
}

小开

最佳答案

你可以使用Floyd的循环查找算法，也就是龟兔算法 其思想是对列表有两个引用，并在不同的速度处移动它们。一个节点通过1向前移动，另一个节点通过2向前移动。< / p >

如果链表中有一个循环they will 肯定 meet.
否则任意一个这两个引用(或它们的next) 将变成null。

实现算法的Java函数:

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;
}
}

小开

我看不出有任何方法可以让这花费固定的时间或空间，两者都会随着列表的大小而增加。

我将使用IdentityHashMap(假设还没有IdentityHashSet)并将每个节点存储到映射中。在存储节点之前，您可以对其调用containsKey。如果节点已经存在，则有一个周期。

ItentityHashMap使用==而不是.equals，这样你就可以检查对象在内存中的位置，而不是它是否具有相同的内容。

小开

乌龟和兔子的另一种解决方案，不太好，因为我暂时改变了列表:

这个想法是遍历列表，并在执行过程中反转它。然后，当你第一次到达一个已经被访问过的节点时，它的next指针将指向“向后”，导致迭代再次朝first前进，并在那里终止。

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 list
cur = 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);
}

小开

public boolean hasLoop(Node start){
TreeSet<Node> set = new TreeSet<Node>();
Node lookingAt = start;


while (lookingAt.peek() != null){
lookingAt = lookingAt.next;


if (set.contains(lookingAt){
return false;
} else {
set.put(lookingAt);
}


return true;
}
// Inside our Node class:
public Node peek(){
return this.next;
}

请原谅我的无知(我对Java和编程仍然相当陌生)，但为什么上面的方法不能工作呢?

我想这并不能解决恒定空间的问题……但它至少在合理的时间内到达那里，对吗?它将只占用链表的空间加上包含n个元素的集合的空间(其中n是链表中元素的数量，或者到达循环之前的元素数量)。对于时间，最坏情况分析，我认为是O(nlog(n))SortedSet对contains()的查找是log(n)(检查javadoc，但我非常确定TreeSet的底层结构是TreeMap，它又是一个红黑树)，在最坏的情况下(没有循环，或在最后循环)，它将不得不进行n次查找。

小开

如果允许我们嵌入类Node，我将像下面实现的那样解决这个问题。hasLoop()在O(n)时间内运行，并且只占用counter的空间。这是不是一个合适的解决方案?或者有一种不嵌入Node的方法吗?(显然，在真正的实现中会有更多的方法，如RemoveNode(Node n)等。)

public class LinkedNodeList {
Node first;
Int count;


LinkedNodeList(){
first = null;
count = 0;
}


LinkedNodeList(Node n){
if (n.next != null){
throw new error("must start with single node!");
} else {
first = n;
count = 1;
}
}


public void addNode(Node n){
Node lookingAt = first;


while(lookingAt.next != null){
lookingAt = lookingAt.next;
}


lookingAt.next = n;
count++;
}


public boolean hasLoop(){


int counter = 0;
Node lookingAt = first;


while(lookingAt.next != null){
counter++;
if (count < counter){
return false;
} else {
lookingAt = lookingAt.next;
}
}


return true;


}






private class Node{
Node next;
....
}


}

小开

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

这是修正后的算法。

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;
}
}

小开

下面是快速/慢速解决方案的改进，它正确地处理奇数长度的列表并提高了清晰度。

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
}

小开

检测链表中的循环可以用最简单的方法之一来完成，使用hashmap会导致O(N)复杂度，使用基于排序的方法会导致O(NlogN)复杂度。

当您从head开始遍历列表时，创建一个已排序的地址列表。当您插入一个新地址时，检查该地址是否已经在已排序的列表中，这需要O(logN)复杂度。

小开

您甚至可以在常数O(1)时间内完成(尽管它不是非常快或有效):计算机内存可以容纳的节点数量是有限的，比如N条记录。如果遍历超过N条记录，那么就有一个循环。

小开

public boolean isCircular() {


if (head == null)
return false;


Node temp1 = head;
Node temp2 = head;


try {
while (temp2.next != null) {


temp2 = temp2.next.next.next;
temp1 = temp1.next;


if (temp1 == temp2 || temp1 == temp2.next)
return true;


}
} catch (NullPointerException ex) {
return false;


}


return false;


}

小开

优于Floyd算法

Richard Brent描述了一个交替周期检测算法，它很像兔子和乌龟[弗洛伊德的周期]，除了，这里的慢节点不移动，但后来被“传送”了。到快速节点的位置在固定的间隔。

描述可在布伦特周期检测算法(瞬移海龟)。布伦特声称他的算法比弗洛伊德的循环算法快24%到36%。 O(n)时间复杂度，O(1)空间复杂度

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

Node slow = root, fast = root;
int taken = 0, limit = 2;
    

while (fast.next != null) {
fast = fast.next;
taken++;
if (slow == fast) return true;
        

if (taken == limit) {
taken = 0;
limit <<= 1;    // equivalent to limit *= 2;
slow = fast;    // teleporting the turtle (to the hare's position)
}
}
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)

小开

我可能会非常晚和新的处理这个线程。但还是. .

为什么不能将节点的地址和“下一个”节点指向存储在表中

如果我们可以这样做

node present: (present node addr) (next node address)


node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

这样就形成了一个循环。

小开

这种方法有空间开销，但实现更简单:

循环可以通过在Map中存储节点来标识。在放置节点之前;检查节点是否已经存在。如果节点已经存在于映射中，则意味着链表有循环。

public boolean loopDetector(Node<E> first) {
Node<E> t = first;
Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();
while (t != null) {
if (map.containsKey(t)) {
System.out.println(" duplicate Node is --" + t
+ " having value :" + t.data);


return true;
} else {
map.put(t, t);
}
t = t.next;
}
return false;
}

小开

这是我的可运行代码。

我所做的是通过使用三个临时节点(空间复杂度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));
}
}

小开

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
Node slower, faster;
slower = head;
faster = head.next; // start faster one node ahead
while (true) {


// if the faster pointer encounters a NULL element
if (faster == null || faster.next == null)
return false;
// if faster pointer ever equals slower or faster's next
// pointer is ever equal to slower then it's a circular list
else if (slower == faster || slower == faster.next)
return true;
else {
// advance the pointers
slower = slower.next;
faster = faster.next.next;
}
}
}

小开

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

< p > 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
}

小开

boolean hasCycle(Node head) {


boolean dec = false;
Node first = head;
Node sec = head;
while(first != null && sec != null)
{
first = first.next;
sec = sec.next.next;
if(first == sec )
{
dec = true;
break;
}


}
return dec;
}

使用上述函数在java中检测linkedlist中的循环。

小开

这是我在java中的解决方案

boolean detectLoop(Node head){
Node fastRunner = head;
Node slowRunner = head;
while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
fastRunner = fastRunner.next.next;
slowRunner = slowRunner.next;
if(fastRunner == slowRunner){
return true;
}
}
return false;
}

小开

你也可以使用上述答案中所建议的弗洛伊德乌龟算法。

这个算法可以检查一个单链表是否有一个闭合循环。这可以通过迭代带有两个移动速度不同的指针的列表来实现。这样，如果存在一个循环，这两个指针将在未来的某个时间点相遇

请随意查看我的链表数据结构上的博客，在那里我还包括了一个用java语言实现上述算法的代码片段。

问候,

安德烈亚斯(@xnorcode)

小开

下面是检测循环的解决方案。

public boolean hasCycle(ListNode head) {
ListNode slow =head;
ListNode fast =head;


while(fast!=null && fast.next!=null){
slow = slow.next; // slow pointer only one hop
fast = fast.next.next; // fast pointer two hops


if(slow == fast)    return true; // retrun true if fast meet slow pointer
}


return false; // return false if fast pointer stop at end
}

小开

在这个上下文中，到处都有文本材料的加载。我只是想张贴一个图表表示，真正帮助我掌握概念。

当快、慢在点p相遇时，

快速行进的距离= a+b+c+b = a+2b+c

慢行距离= a+b

因为快的比慢的快2倍。所以A +2b+c = 2(A +b)，然后我们得到c =.

因此，当另一个慢速指针再次从前往q运行时，同时，快速指针将从P到q运行，因此它们在问会合。

public ListNode detectCycle(ListNode head) {
if(head == null || head.next==null)
return null;


ListNode slow = head;
ListNode fast = head;


while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;


/*
if the 2 pointers meet, then the
dist from the meeting pt to start of loop
equals
dist from head to start of loop
*/
if (fast == slow){ //loop found
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}

小开

//链表查找循环函数

int findLoop(struct Node* head)
{
struct Node* slow = head, *fast = head;
while(slow && fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return 1;
}
return 0;
}

小开

如果链表结构实现了java.util.List. list。我们可以使用列表大小来跟踪我们在列表中的位置。

我们可以遍历节点，将当前节点的位置与上一个节点的位置进行比较。如果我们当前的位置超过了上一个位置，我们就检测到列表在某个地方有一个循环。

这种解决方案需要恒定的空间，但随着列表大小的增加，完成所需的时间会线性增加。


class LinkedList implements List {
Node first;
int listSize;
    

@Override
int size() {
return listSize;
}


[..]


boolean hasLoop() {
int lastPosition = size();
int currentPosition = 1;
Node next = first;
while(next != null) {
if (currentPosition > lastPosition) return true;
next = next.next;
currentPosition++;
}
return false;
}
}

或作为一种实用工具:

static boolean hasLoop(int size, Node first) {
int lastPosition = size;
int currentPosition = 1;
Node next = first;
while(next != null) {
if (currentPosition > lastPosition) return true;
next = next.next;
currentPosition++;
}
return false;
}

小开

我不确定这个答案是否适用于Java，但我仍然认为它属于这里:

当我们在现代体系结构中使用指针时，我们可以期望它们是CPU字对齐。对于64位体系结构，这意味着指针的前3位始终为零。这让我们可以使用这个内存来标记我们已经见过的指针，通过对它们的第一个比特写入1。

如果我们遇到一个指针，它的第一个位已经写了1，那么我们已经成功地找到了一个循环，之后我们需要再次遍历结构，并将这些位屏蔽掉。完成了!

这种方法被称为指针标记，它在低级编程中被过度使用，例如Haskell在一些优化中使用它。

小开

func checkLoop(_ head: LinkedList) -> Bool {
var curr = head
var prev = head
    

while curr.next != nil, curr.next!.next != nil {
curr = (curr.next?.next)!
prev = prev.next!
        

if curr === prev {
return true
}
}
    

return false
}