假设您在 Java 中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
并且每个Node都指向下一个节点,除了最后一个Node,它的next为null。假设列表有可能包含一个循环 - 即最终节点,而不是 null,具有对列表中在它之前的节点之一的引用。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定节点是带有循环的列表的第一个,则返回 true
,否则返回 false
?你怎么能写出来,让它占用恒定的空间和合理的时间?
这是带有循环的列表的图片:
您可以使用Floyd's cycle-finding algorithm ,也称为龟兔算法。
这个想法是有两个对列表的引用并以不同的速度移动它们。一个向前移动 1
节点,另一个向前移动 2
节点。
- 如果链表有循环,它们一定会见面的。
- 其他任何一个两个引用(或它们的
next
)将变为 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;
}
}
我是一名优秀的程序员,十分优秀!