假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回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 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)
这样就形成了一个循环。
乌龟和兔子的另一种解决方案，不太好，因为我暂时改变了列表:
这个想法是遍历列表，并在执行过程中反转它。然后，当你第一次到达一个已经被访问过的节点时，它的next指针将指向“向后”，导致迭代再次朝第一个方向进行，并在那里终止。
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);
}
这是我在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;
}
我看不出有任何方法可以让这花费固定的时间或空间，两者都会随着列表的大小而增加。
我将使用IdentityHashMap(假设还没有IdentityHashSet)并将每个节点存储到映射中。在存储节点之前，您可以对其调用containsKey。如果节点已经存在，则有一个周期。
ItentityHashMap使用==而不是.equals，这样你就可以检查对象在内存中的位置，而不是它是否具有相同的内容。
下面是快速/慢速解决方案的改进，它正确地处理奇数长度的列表并提高了清晰度。
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
}
