在单链表中查找循环
如何检测单链表是否有循环？如果它有循环，那么如何找到循环的起始点，即循环开始的节点。
回答 13
Stack Overflow用户
发布于 2012-04-23 14:08:04
你可以通过简单地在列表中运行两个指针来检测它，这个过程被称为乌龟和野兔算法，以同名的寓言命名：
- 首先检查列表是否为空(
head为null)。如果是，则不存在循环，因此停止now. - Otherwise，在第一节点
head.next. - Then上开始第一指针
tortoise，并且在第二节点head上的第二指针hare连续循环，直到hare为null(在单元素列表中可能已经为真)，在每次迭代中将tortoise前进1，将hare前进2。野兔肯定会最先到达终点(如果有终点)，因为它在前面启动，并且运行得更快。 - 如果没有终点(即，如果有循环)，它们最终将指向同一个节点，您可以停止，因为您知道在周期内的某个地方找到了一个节点。
考虑以下从3开始的循环
head -> 1 -> 2 -> 3 -> 4 -> 5
^ |
| V
8 <- 7 <- 6从从1开始的tortoise和从2开始的hare，它们采用以下值：
(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).这是下面的流程：
- Advance
hare并将size设置为1. - Then，只要
hare和tortoise不同，就继续前进hare，每次都会增加size。这最终给出了周期的大小，在本例中是6。 - 在这一点上，如果
size为1，这意味着你必须已经在周期的开始处(在大小为1的周期中，只有一个可能的节点在周期中，所以它必须是第一个节点)。在本例中，您只需返回hare作为开始，并跳过其余步骤，将hare和tortoise都设置为列表的第一个元素，并精确地前进haresize次(在本例中为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)。
如果您想要更正式地证明此方法有效，可以查看以下资源：
我们姐妹网站上的
- a question；
- Wikipedia cycle detection页面；或
- 的“乌龟和野兔算法”，彼得·伽米，2016年4月17日。
如果您只是想获得对该方法的支持(而不是正式的证明)，那么可以运行以下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))
breakStack Overflow用户
发布于 2014-02-12 10:58:49
选择的答案给出了一个O(n*n)的解决方案来寻找循环的开始节点。这是一个O(n)解决方案：
一旦我们发现慢的A和快的B在循环中相遇，让它们中的一个静止，而另一个继续前进，每次走一步，以确定循环的周长，例如，P。
然后我们把一个节点放在头上，让它走P步，然后把另一个节点放在头上。我们每次都将这两个节点向前推进一步，当它们第一次相遇时，它是循环的起点。
Stack Overflow用户
发布于 2014-05-11 17:56:11
也可以使用hash map来判断链表是否有循环，下面函数使用hash map来判断链表是否有循环
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)空间复杂度。
https://stackoverflow.com/questions/10275587
复制相似问题
腾讯云开发者
