如何检测链表中的循环？
假设你有一个Java链接列表结构。 它由节点组成：
class Node { Node next; // some user data } 每个节点指向下一个节点，除了最后一个节点，下一个节点为空。 说有可能列表可以包含一个循环 – 即最后一个节点，而不是一个空，有一个参考列表中的其中一个节点之前。
什么是最好的写作方式
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表中的第一个，则返回true否则返回false ？ 你怎么写，以便它需要一个恒定的空间和合理的时间？
下面是一个循环列表的图片：
你可以利用弗洛伊德的循环寻找algorithm ，也被称为乌龟和兔子algorithm 。
这个想法是有两个引用列表，并以不同的速度移动它们。 向前移动1节点，另一个移动2节点。
- 如果链表有一个循环，他们一定会见面。
- 否则两个引用（或其
next）中的任何next将变为null。
实现该algorithm的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; } }
下面是Fast / Slow解决scheme的一个改进，它可以正确处理奇数长度的列表并提高清晰度。
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 }
乌龟和兔子的替代解决scheme，不如我暂时改变列表：
这个想法是走在清单上，并随时撤销。 然后，当你第一次到达一个已经被访问过的节点时，它的下一个指针将指向“向后”，导致迭代继续向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;
testing代码：
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); }
比弗洛伊德的algorithm更好
理查德·布伦特（Richard Brent）描述了一种替代的循环检测algorithm ，它与野兔和乌龟（弗洛伊德的循环）非常相似，只是这里的慢节点不动，而后被“传送”到固定的快节点位置间隔。
描述可以在这里find： http : //www.siafoo.net/algorithm/11 Brent声称他的algorithm比Floyd的循环algorithm快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; }
乌龟和野兔
看看Pollard的rhoalgorithm 。 这不是一个相同的问题，但也许你会理解它的逻辑，并将其应用于链表。
（如果你是懒惰的，你可以检查周期检测 – 检查关于乌龟和野兔的部分。）
这只需要线性时间和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; }
（大多数解决scheme不检查next和next.next是否为null，而且，因为龟总是在后面，所以你不必检查它是否为空 – 野兔已经这样做了。）
用户unicornaddict上面有一个很好的algorithm，但不幸的是，它包含一个奇怪长度大于等于3的非loopy列表的bug。问题是fast可能会在列表结束之前“卡住”， slow赶上它，并且（错误地）检测到循环。
这是更正后的algorithm。
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（n ^ 2）。 但是，它应该有助于完成工作（最终）。
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++; }
algorithm
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)
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和编程还相当陌生），但是为什么上面不工作呢？
我想这不能解决恒定的空间问题，但它至less在合理的时间内到达那里，对吗？ 它只会将链表的空间加上一个具有n个元素的集合的空间（其中n是链表中元素的个数，或者直到达到一个循环的元素的个数）。 而就时间而言，我认为最糟糕的情况分析会显示O（nlog（n））。 对于contains（）的SortedSet查找是log（n）（检查javadoc，但是我非常确定TreeSet的底层结构是TreeMap，它又是一棵红黑树），在最坏的情况下（没有循环，或在最后循环），它将不得不做n查找。
如果我们被允许embedded类Node ，我会解决这个问题，因为我已经在下面实现了。 hasLoop()运行在O（n）时间，只占用counter的空间。 这似乎是一个合适的解决scheme？ 或者有没有一种方法来做到这一点，而不embeddedNode ？ （显然，在一个真正的实现中会有更多的方法，像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; .... } }
你甚至可以在恒定的O（1）时间内完成这个工作（虽然它不会很快或者很高效）：Nlogging表明，你的计算机内存可以容纳的节点数量是有限的。 如果遍历N个以上的logging，那么你有一个循环。
// 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; } } }
我看不出有什么办法让这个占用一定的时间或空间，两者都会随着列表的大小而增加。
我会利用一个IdentityHashMap（假设还没有一个IdentityHashSet）并将每个Node存储到地图中。 在存储节点之前，您将调用containsKey。 如果节点已经存在，你有一个循环。
ItentityHashMap使用==而不是.equals，以便检查对象在内存中的位置，而不是如果内容相同。
我认为这可以通过O（n）复杂性最简单的方式之一来完成。
当你从头开始遍历列表时，创build一个sorting的地址列表。 当你插入一个新的地址，只要检查它已经在sorting列表中。 sorting只有O（logN）复杂性:-)
我可能是非常晚，新来处理这个线程。 但还是..
为什么不能将节点的地址和指向的“下一个”节点存储在表中
如果我们可以这样列表
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)
因此形成了一个循环。
这是我的可运行代码。
我所做的是通过使用三个临时节点（空间复杂度O(1) ）来追踪链接，从而对链接列表进行尊重。
有趣的事实是帮助检测链表中的循环，因为随着前进，你不会期望回到起点（根节点），临时节点之一应该为空，除非你有一个循环，这意味着它指向根节点。
该algorithm的时间复杂度为O(n) ，空间复杂度为O(1) 。
这是链表的类节点：
public class LinkedNode{ public LinkedNode next; }
下面是一个包含三个节点的简单testing案例的主要代码，最后一个节点指向第二个节点：
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; }
下面是一个简单的三个节点的testing案例，最后一个节点指向第二个节点：
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)); } }
这个代码被优化，并且产生的结果比被select为最佳答案的结果更快。这个代码可以省去追逐前进和后退节点指针的很长的过程，如果遵循“最佳回答'的方法。通过下面的干运行，你会明白我想说什么。然后通过下面给出的方法来看问题，并衡量没有。 采取了哪些步骤来find答案。
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中的链表中的循环。
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; }
这种方法有空间开销，但更简单的实现：
循环可以通过在一个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; }
这是我在java中的解决scheme
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; }
