假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回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中的循环。
其他回答
//链表查找循环函数
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;
}
这种方法有空间开销，但实现更简单:
循环可以通过在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));
}
}
这是我在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;
}
你可以使用弗洛伊德的周期寻找算法，也被称为乌龟和野兔算法。 其思想是对列表有两个引用，并以不同的速度移动它们。一个向前移动1个节点，另一个向前移动2个节点。
如果链表有一个循环 一定会见面的。 或者 这两个引用(或下一个) 将变为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;
}
}
