如何检测单链表是否有循环？如果它有循环，那么如何找到循环的起点，即循环开始的节点。
问问题
77138 次
13 回答
133
您可以通过简单地在列表中运行两个指针来检测它，这个过程在同名寓言之后被称为龟兔算法：
- 首先，检查列表是否为空（
headisnull）。如果是这样，则不存在循环，所以现在停止。 - 否则，在第一个节点上启动第一个指针
tortoise，在第二个节点上启动第二head个指针。harehead.next - 然后连续循环直到
hareisnull（在单元素列表中可能已经是真的），在每次迭代中前进tortoise一和二。hare保证兔子首先到达终点（如果有终点），因为它开始领先并且跑得更快。 - 如果没有尽头（即，如果有一个循环），它们最终将指向同一个节点并且您可以停止，因为您知道您在循环中的某个位置找到了一个节点。
考虑以下从 开始的循环3：
head -> 1 -> 2 -> 3 -> 4 -> 5
^ |
| V
8 <- 7 <- 6
从tortoise1 和hare2 开始，它们具有以下值：
(tortoise,hare) = (1,2) (2,4) (3,6) (4,8) (5,4) (6,6)
因为它们在 处相等(6,6)，并且由于hare应该始终tortoise在非循环列表中超出，这意味着您已经发现了一个循环。
伪代码将如下所示：
def hasLoop (head):
return false if head = null # Empty list has no loop.
tortoise = head # tortoise initially first element.
hare = tortoise.next # Set hare to second element.
while hare != null: # Go until hare reaches end.
return false if hare.next = null # Check enough left for hare move.
hare = hare.next.next # Move hare forward two.
tortoise = tortoise.next # Move tortoise forward one.
return true if hare = tortoise # Same means loop found.
endwhile
return false # Loop exit means no loop.
enddef
该算法的时间复杂度是O(n)因为访问的节点数（龟兔赛跑）与节点数成正比。
一旦你知道循环中的一个节点，还有一种O(n)方法可以保证找到循环的开始。
在循环中的某处找到一个元素但不确定循环的开始在哪里之后，让我们返回到原始位置。
head -> 1 -> 2 -> 3 -> 4 -> 5
^ |
| V
8 <- 7 <- 6
\
x (where hare and tortoise met).
这是要遵循的过程：
- 前进
hare并设置size为1。 - 然后，只要
hare和tortoise不同，就不断前进hare，size每次递增。这最终给出了循环的大小，在这种情况下为六。 - 此时，如果
sizeis1，则意味着您必须已经处于循环的开始（在大小为 1 的循环中，只有一个可能的节点可以在循环中，因此它必须是第一个）。在这种情况下，您只需hare从头返回，然后跳过下面的其余步骤。 - 否则，将
hare和都设置为列表tortoise的第一个元素并hare准确推进size时间（7在本例中为 ）。这给出了两个指针，它们完全不同的循环大小。 - 然后，只要
hare和tortoise不同，就将它们一起推进（兔子以更平稳的速度奔跑，与乌龟的速度相同 - 我猜它从第一次跑步就累了）。由于它们将始终保持size彼此完全分开的元素，tortoise因此将与返回到循环开始的时间完全相同地到达循环的开始。hare
您可以通过以下演练看到这一点：
size tortoise hare comment
---- -------- ---- -------
6 1 1 initial state
7 advance hare by six
2 8 1/7 different, so advance both together
3 3 2/8 different, so advance both together
3/3 same, so exit loop
因此3是循环的起点，并且由于这两个操作（循环检测和循环开始发现）都是O(n)按顺序执行的，所以整个事情也都是O(n)。
如果您想要一个更正式的证明这有效，您可以检查以下资源：
如果您只是在支持该方法（不是正式证明）之后，您可以运行以下 Python 3 程序，该程序评估其对大量尺寸（循环中有多少元素）和引入（元素之前的元素）的可操作性循环开始）。
你会发现它总能找到两个指针相交的点：
def nextp(p, ld, sz):
if p == ld + sz:
return ld
return p + 1
for size in range(1,1001):
for lead in range(1001):
p1 = 0
p2 = 0
while True:
p1 = nextp(p1, lead, size)
p2 = nextp(nextp(p2, lead, size), lead, size)
if p1 == p2:
print("sz = %d, ld = %d, found = %d" % (size, lead, p1))
break
于 2012-04-23T06:08:03.910 回答
37
选择的答案给出了一个 O(n*n) 解决方案来找到循环的开始节点。这是一个 O(n) 的解决方案：
一旦我们发现慢 A 和快 B 在循环中相遇，使它们中的一个静止，而另一个每次继续走一步，以确定循环的周长，例如，P。
然后我们把一个节点放在头部，让它走P步，然后把另一个节点放在头部。我们将这两个节点每次都推进一步，当它们第一次相遇时，它就是循环的起点。
于 2014-02-12T02:58:49.483 回答
7
您也可以使用哈希映射来查找链接列表是否有循环下面的函数使用哈希映射来找出链接列表是否有循环
static bool isListHaveALoopUsingHashMap(Link *headLink) {
map<Link*, int> tempMap;
Link * temp;
temp = headLink;
while (temp->next != NULL) {
if (tempMap.find(temp) == tempMap.end()) {
tempMap[temp] = 1;
} else {
return 0;
}
temp = temp->next;
}
return 1;
}
两个指针方法是最好的方法，因为时间复杂度是 O(n) Hash Map 需要额外的 O(n) 空间复杂度。
于 2014-05-11T09:56:11.040 回答
3
我在 Narasimha Karamanchi 的数据结构书中读到了这个答案。
我们可以使用Floyd 循环寻找算法，也称为龟兔算法。在这里，使用了两个指针；一个（比如slowPtr）由单个节点推进，另一个（比如fastPtr）由两个节点推进。如果单链表中存在任何循环，它们肯定会在某个时候相遇。
struct Node{
int data;
struct Node *next;
}
// program to find the begin of the loop
int detectLoopandFindBegin(struct Node *head){
struct Node *slowPtr = head, *fastPtr = head;
int loopExists = 0;
// this while loop will find if there exists a loop or not.
while(slowPtr && fastPtr && fastPtr->next){
slowPtr = slowPtr->next;
fastPtr = fastPtr->next->next;
if(slowPtr == fastPtr)
loopExists = 1;
break;
}
如果存在任何循环，那么我们将其中一个指针指向头部，现在将它们都推进一个节点。他们将相遇的节点将是单链表中循环的开始节点。
if(loopExists){
slowPtr = head;
while(slowPtr != fastPtr){
fastPtr = fastPtr->next;
slowPtr = slowPtr->next;
}
return slowPtr;
}
return NULL;
}
于 2017-12-19T10:04:15.757 回答
2
在大多数情况下，所有先前的答案都是正确的，但这里是带有可视化和代码的逻辑的简化版本（适用于 Python 3.7）
正如其他人解释的那样，逻辑非常简单。我要创建乌龟/慢和野兔/快。如果我们以不同的速度移动两个指针，那么最终快会遇到慢！！您也可以将其视为大头针圆形场地中的两个跑步者。如果快跑者继续绕圈，那么它将遇到/超过慢跑者。
因此，我们将在每次迭代中以 1 的速度移动 Tortoise/slow 指针，同时以 2 的速度继续递增或移动 Hare/fast 指针。一旦它们相遇，我们就知道存在一个循环。这也被称为弗洛伊德的循环寻找算法
这是执行此操作的 Python 代码（注意 has_cycle 方法是主要部分）：
#!/usr/bin/env python3
class Node:
def __init__(self, data = None):
self.data = data
self.next = None
def strnode (self):
print(self.data)
class LinkedList:
def __init__(self):
self.numnodes = 0
self.head = None
def insertLast(self, data):
newnode = Node(data)
newnode.next = None
if self.head == None:
self.head = newnode
return
lnode = self.head
while lnode.next != None :
lnode = lnode.next
lnode.next = newnode # new node is now the last node
self.numnodes += 1
def has_cycle(self):
slow, fast = self.head ,self.head
while fast != None:
if fast.next != None:
fast = fast.next.next
else:
return False
slow = slow.next
if slow == fast:
print("--slow",slow.data, "fast",fast.data)
return True
return False
linkedList = LinkedList()
linkedList.insertLast("1")
linkedList.insertLast("2")
linkedList.insertLast("3")
# Create a loop for testing
linkedList.head.next.next.next = linkedList.head;
#let's check and see !
print(linkedList.has_cycle())
于 2019-01-13T04:40:42.860 回答
1
以下代码将查找 SLL 中是否存在循环，如果存在，将返回然后开始节点。
int find_loop(Node *head){
Node * slow = head;
Node * fast = head;
Node * ptr1;
Node * ptr2;
int k =1, loop_found =0, i;
if(!head) return -1;
while(slow && fast && fast->next){
slow = slow->next;
/*Moving fast pointer two steps at a time */
fast = fast->next->next;
if(slow == fast){
loop_found = 1;
break;
}
}
if(loop_found){
/* We have detected a loop */
/*Let's count the number of nodes in this loop node */
ptr1 = fast;
while(ptr1 && ptr1->next != slow){
ptr1 = ptr1->next;
k++;
}
/* Now move the other pointer by K nodes */
ptr2 = head;
ptr1 = head;
for(i=0; i<k; i++){
ptr2 = ptr2->next;
}
/* Now if we move ptr1 and ptr2 with same speed they will meet at start of loop */
while(ptr1 != ptr2){
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr1->data;
}
于 2013-10-16T16:26:24.367 回答
0
boolean hasLoop(Node *head)
{
Node *current = head;
Node *check = null;
int firstPtr = 0;
int secondPtr = 2;
do {
if (check == current) return true;
if (firstPtr >= secondPtr){
check = current;
firstPtr = 0;
secondPtr= 2*secondPtr;
}
firstPtr ++;
} while (current = current->next());
return false;
}
另一个 O(n) 解决方案。
于 2014-09-04T09:39:12.047 回答
0
在查看所选答案时，我尝试了几个示例并发现：
如果 (A1,B1), (A2,B2) ... (AN, BN) 是指针 A 和 B 的遍历，
其中 A 步骤 1 元素B步2个元素，Ai和Bj为A和B遍历的节点，AN=BN。
然后，循环开始的节点是 Ak，其中 k = floor(N/2)。
于 2016-11-23T11:35:40.267 回答
0
好的 - 我昨天在一次采访中遇到了这个问题 - 没有可用的参考资料，我想出了一个非常不同的答案（当然是在开车回家的时候......）因为链接列表通常是使用 malloc 逻辑分配的（我并不总是承认）那么我们知道分配的粒度是已知的。在大多数系统上，这是 8 个字节 - 这意味着底部 3 位始终为零。考虑 - 如果我们将链表放在一个类中以控制访问并使用 0x0E 的掩码 ored 到下一个地址，那么我们可以使用低 3 位来存储中断面包屑因此我们可以编写一个方法来存储我们的最后一个面包屑- 说 1 或 2 - 并交替使用它们。然后，我们检查循环的方法可以逐步遍历每个节点（使用我们的下一个方法）并检查下一个地址是否包含当前的面包屑 - 如果有，我们有一个循环 - 如果没有，那么我们将屏蔽低 3 位并添加我们当前的面包屑。面包屑检查算法必须是单线程的，因为您不能一次运行其中两个，但它会允许其他线程异步访问列表 - 关于添加/删除节点的常见警告。你怎么看？如果其他人认为这是一个有效的解决方案，我可以编写示例类......只是想想有时一种新的方法是好的，并且总是愿意被告知我刚刚错过了重点......谢谢所有标记 面包屑检查算法必须是单线程的，因为您不能一次运行其中两个，但它会允许其他线程异步访问列表 - 关于添加/删除节点的常见警告。你怎么看？如果其他人认为这是一个有效的解决方案，我可以编写示例类......只是想想有时一种新的方法是好的，并且总是愿意被告知我刚刚错过了重点......谢谢所有标记 面包屑检查算法必须是单线程的，因为您不能一次运行其中两个，但它会允许其他线程异步访问列表 - 关于添加/删除节点的常见警告。你怎么看？如果其他人认为这是一个有效的解决方案，我可以编写示例类......只是想想有时一种新的方法是好的，并且总是愿意被告知我刚刚错过了重点......谢谢所有标记
于 2017-10-19T14:22:32.130 回答
0
另一种解决方案
检测循环：
- 创建一个列表
- 循环遍历链表并继续将节点添加到列表中。
- 如果节点已经存在于列表中，我们有一个循环。
去除循环：
- 在上面的第 2 步中，while 循环遍历链表，我们还跟踪前一个节点。
一旦我们在步骤#3 中检测到循环，将前一个节点的下一个值设置为 NULL
＃代码
def detect_remove_loop（头）
cur_node = head node_list = [] while cur_node.next is not None: prev_node = cur_node cur_node = cur_node.next if cur_node not in node_list: node_list.append(cur_node) else: print('Loop Detected') prev_node.next = None return print('No Loop detected')
于 2018-07-28T07:05:35.507 回答
0
首先，创建一个节点
struct Node {
int data;
struct Node* next;
};
全局初始化头指针
Struct Node* head = NULL;
在链表中插入一些数据
void insert(int newdata){
Node* newNode = new Node();
newNode->data = newdata;
newNode->next = head;
head = newNode;
}
创建一个函数detectLoop()
void detectLoop(){
if (head == NULL || head->next == NULL){
cout<< "\nNo Lopp Found in Linked List";
}
else{
Node* slow = head;
Node* fast = head->next;
while((fast && fast->next) && fast != NULL){
if(fast == slow){
cout<<"Loop Found";
break;
}
fast = fast->next->next;
slow = slow->next;
}
if(fast->next == NULL){
cout<<"Not Found";
}
}
}
从 main() 调用函数
int main()
{
insert(4);
insert(3);
insert(2);
insert(1);
//Created a Loop for Testing, Comment the next line to check the unloop linkedlist
head->next->next->next->next = head->next;
detectLoop();
//If you uncomment the display function and make a loop in linked list and then run the code you will find infinite loop
//display();
}
于 2019-04-23T06:33:22.737 回答
0
bool FindLoop(struct node *head)
{
struct node *current1,*current2;
current1=head;
current2=head;
while(current1!=NULL && current2!= NULL && current2->next!= NULL)
{
current1=current1->next;
current2=current2->next->next;
if(current1==current2)
{
return true;
}
}
return false;
}
于 2019-06-18T10:15:37.447 回答
-1
一种完全不同的方法：- 反转链表。倒车时，如果您再次到达头部，则列表中有一个循环，如果您获得 NULL，则没有循环。总时间复杂度为 O(n)
于 2016-02-06T05:10:47.200 回答