"Removing loop from Linked List"运行时错误

Question

我正在尝试以下代码挑战：

您将获得N节点的链接列表。任务是从链接列表中删除循环(如果存在(。

注意：C是最后一个节点连接到的节点的位置。如果它是0，则没有循环。

示例1：

输入：

N = 3
value[] = {1,3,4}
C = 2

输出：1

解释：在第一个测试用例中N=3.带节点的链表N＝3。这里，x=2表示最后一个节点与xth连接链表的节点。因此存在一个循环。

示例2：

输入：

N = 4
value[] = {1,8,3,4}
C = 0

输出：1

解释：N=4和x=0表示lastNode->next=NULL，因此链接列表不包含任何循环。

您的任务：

您的任务是完成函数removeLoop()。该函数的唯一参数是链表的头指针。只需删除列表中的循环(如果存在(，而不从列表中断开任何节点的连接。如果您的代码正确，驱动程序代码将打印1。

预期时间复杂度：O(n(

预期辅助空间：O(1(

限制条件：

1 <= N <= 104

我的代码：

'''
class Node:
def __init__(self,val):
self.next=None
self.data=val
'''
def removeLoop(head):
slow = fast = head
while fast!=None and fast.next!=None:
slow = slow.next
fast = fast.next.next
if slow==fast:
x = slow
temp = head
while x.next!=temp.next:
x = x.next
temp = temp.next
x.next = None
return head

我遇到运行时错误。有人能告诉我为什么吗？

Answer 1

有几个问题：

• 当列表没有循环时，则在中未定义x

  while x.next!=temp.next:
  

• 当列表有一个循环时，第一个循环永远不会退出。

• 当循环包括所有节点("尾部"链接回第一个节点(时，此代码将断开头部节点和第二个节点之间的链接，这显然是错误的。这是一个需要单独解决的边界情况。

前两个问题深入到缩进问题。第二个while循环应仅在检测到循环时执行。最简单的方法是将其移动到检测到循环的if中，同时使用return语句：

def removeLoop(head):
slow = fast = head
while fast!=None and fast.next!=None:
slow = slow.next
fast = fast.next.next
if slow==fast:
if slow == head:  # special case
# find the "tail" node
while slow.next != head:
slow = slow.next
else:
while slow.next != head.next:
slow = slow.next
head = head.next
slow.next = None
return

据我所知，不需要返回任何值，因此不需要返回head。

示例运行

以下是用一些样板代码完成的代码，以及针对以下问题的运行：

N = 5
value[] = {7,58,36,34,16}
C = 1

因此，这代表了以下带有循环的列表：

7 → 58 → 36
↑         ↓
16   ←   34     

removeLoop函数将删除16和7之间的链接。

class Node:
def __init__(self, val):
self.val = val
self.next = None
def print(self):
node = self
for _ in range(10):
if not node:
break
print(node.val, end=" ")
node = node.next
print("..." if node else "")
def createLinkedList(values, cycle_start_index):
# create all nodes
nodes = [Node(val) for val in values]
for i, node in enumerate(nodes):
if i:  # link node from previous
nodes[i-1].next = node
if cycle_start_index > 0:  # create the cycle
nodes[-1].next = nodes[cycle_start_index-1]  # 1-based index
return nodes[0]
def removeLoop(head):
slow = fast = head
while fast!=None and fast.next!=None:
slow = slow.next
fast = fast.next.next
if slow==fast:
if slow == head:  # special case
# find the "tail" node
while slow.next != head:
slow = slow.next
else:
while slow.next != head.next:
slow = slow.next
head = head.next
slow.next = None
return
# demo
lst = createLinkedList([7, 58, 36, 34, 16], 1)
lst.print()  # 7 58 36 34 16 58 36 34 16 58 ...
removeLoop(lst)
lst.print()  # 7 58 36 34 16