假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
这是我在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;
}
其他回答
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
}
如果允许我们嵌入类Node，我将像下面实现的那样解决这个问题。hasLoop()在O(n)时间内运行，并且只占用计数器的空间。这是不是一个合适的解决方案?或者是否有一种不嵌入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;
....
}
}
下面是快速/慢速解决方案的改进，它正确地处理奇数长度的列表并提高了清晰度。
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
}
//链表查找循环函数
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;
}
我读了一些答案，人们忽略了上述问题的一个明显的解决方案。
如果给定我们可以改变类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;
}
