假设您在Java中有一个链表结构。它由节点组成:
class Node {
Node next;
// some user data
}
每个节点都指向下一个节点，除了最后一个节点，它的next为空。假设有一种可能性，列表可以包含一个循环-即最后的节点，而不是有一个空值，有一个引用到列表中它之前的一个节点。
最好的写作方式是什么
boolean hasLoop(Node first)
如果给定的节点是带有循环的列表的第一个，则返回true，否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?
下面是一个带有循环的列表的图片:
当前回答
public boolean isCircular() {
if (head == null)
return false;
Node temp1 = head;
Node temp2 = head;
try {
while (temp2.next != null) {
temp2 = temp2.next.next.next;
temp1 = temp1.next;
if (temp1 == temp2 || temp1 == temp2.next)
return true;
}
} catch (NullPointerException ex) {
return false;
}
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。此外，因为乌龟总是在后面，你不需要检查它是否为空——兔子已经检查过了。)
下面的方法可能不是最好的——它是O(n²)。然而，它应该有助于完成工作(最终)。
count_of_elements_so_far = 0;
for (each element in linked list)
{
search for current element in first <count_of_elements_so_far>
if found, then you have a loop
else,count_of_elements_so_far++;
}
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
}
// To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
Node slower, faster;
slower = head;
faster = head.next; // start faster one node ahead
while (true) {
// if the faster pointer encounters a NULL element
if (faster == null || faster.next == null)
return false;
// if faster pointer ever equals slower or faster's next
// pointer is ever equal to slower then it's a circular list
else if (slower == faster || slower == faster.next)
return true;
else {
// advance the pointers
slower = slower.next;
faster = faster.next.next;
}
}
}
检测链表中的循环可以用最简单的方法之一来完成，使用hashmap会导致O(N)复杂度，使用基于排序的方法会导致O(NlogN)复杂度。
当您从head开始遍历列表时，创建一个已排序的地址列表。当您插入一个新地址时，检查该地址是否已经在已排序的列表中，这需要O(logN)复杂度。
