假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
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和编程仍然相当陌生)，但为什么上面的方法不能工作呢?
I guess this doesn't solve the constant space issue... but it does at least get there in a reasonable time, correct? It will only take the space of the linked list plus the space of a set with n elements (where n is the number of elements in the linked list, or the number of elements until it reaches a loop). And for time, worst-case analysis, I think, would suggest O(nlog(n)). SortedSet look-ups for contains() are log(n) (check the javadoc, but I'm pretty sure TreeSet's underlying structure is TreeMap, whose in turn is a red-black tree), and in the worst case (no loops, or loop at very end), it will have to do n look-ups.
其他回答
您甚至可以在常数O(1)时间内完成(尽管它不是非常快或有效):计算机内存可以容纳的节点数量是有限的，比如N条记录。如果遍历超过N条记录，那么就有一个循环。
下面是检测循环的解决方案。
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
}
我可能会非常晚和新的处理这个线程。但还是. .
为什么不能将节点的地址和“下一个”节点指向存储在表中
如果我们可以这样做
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)
这样就形成了一个循环。
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
}
乌龟和兔子
看看波拉德的算法。这不是完全相同的问题，但也许你会理解其中的逻辑，并将其应用于链表。
(如果你很懒，你可以看看周期检测——看看关于乌龟和兔子的那部分。)
这只需要线性时间和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。此外，因为乌龟总是在后面，你不需要检查它是否为空——兔子已经检查过了。)
