如何解决Linked list found cycle error

Question

下面的代码是为了解决 leetcode 中的 Rotate List 问题而编写的，但是我的代码抛出“在 ListNode 中找到循环”错误。 我找不到哪条线正在创建循环，帮助！

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
  def rotateRight(self, head, k):
    """
    :type head: ListNode
    :type k: int
    :rtype: ListNode
    """
    # visualiser   =    prev -> curr -> nxt
    # ListNode [1,2,3]   2       3      None


    dummy = prev = ListNode(0, head)   #create a new node, its next node = head
    curr, nxt = head, head.next
    while curr and k > 0: 
        if nxt == None:
            prev.next = nxt
            curr.next = dummy.next
            dummy.next = curr
            k -= 1
        else:
            prev = prev.next
            curr = curr.next
            nxt = nxt.next
    return dummy.next

Answer 1

if nxt == None:

块正确执行第一次旋转，但在第二次旋转时出现问题。当时

prev

和

curr

仍然引用它们在第一次旋转时引用的节点，所以现在

curr

是链表的first节点。但这意味着声明

curr.next = dummy.next

创建了一个自我引用！

可视化可能会有所帮助。就在第一次旋转发生之前，我们有这个状态：

dummy            prev curr  nxt
   ↓               ↓   ↓     ↓
   0 → 1 → 2 → 3 → 4 → 5 → None 

第一次轮换后，我们有这个：

dummy curr           prev   nxt
   ↓   ↓               ↓     ↓
   0 → 5 → 1 → 2 → 3 → 4 → None

这也是第二次轮换开始前的状态。执行

curr.next = dummy.next

时引入循环：

dummy curr           prev   nxt
   ↓   ↓               ↓     ↓
   0 → 5 ┐ 1 → 2 → 3 → 4 → None
       └─┘

任何进一步的旋转将不再修改列表。你真正想要的是组合

prev, curr

会“后退一步”，但这并不容易做到，因为我们没有对

prev

的前身的引用。所以简而言之，我们需要一种不同的方法。

老实说，虚拟节点对这个问题没有帮助。

不需要对

k

属性执行

next

次更新。这可以通过仅改变两个节点来完成。主要思想是使列表循环，然后将

head

引用设置为其他节点之一（取决于

k

），然后再次打破循环。此外，通过意识到全方位旋转是无用的，确保减少 k 的

huge

值。例如，在 5 个节点的列表中，进行 721 次旋转与进行 1 次旋转具有相同的结果。

这里是一个实现：

class Solution(object):
  def rotateRight(self, head, k):
    # boundary case
    if not head or not head.next:
      return head
   
    # get tail and size of list
    tail = head
    size = 1
    while tail.next:
      size += 1
      tail = tail.next

    # temporarily make list circular
    tail.next = head

    # get the node that will be the new tail
    tail = head
    for _ in range(size - k%size - 1):
      tail = tail.next

    # break cycle after new tail
    head = tail.next
    tail.next = None

    return head