求解LeetCode旋转链表问题时出现ListNode循环错误，求排查

我写了一段代码解决LeetCode上的「旋转链表」问题，但运行时抛出了“Found cycle in the 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

循环产生的原因 #

你的代码在处理链表末尾时，会执行curr.next = dummy.next，第一次旋转后dummy.next已经指向了curr（原链表尾节点）。当k大于链表长度时，后续循环会再次进入nxt == None的分支，此时curr还是那个尾节点，执行curr.next = dummy.next就会让curr的next指向自己，直接形成循环链表，触发LeetCode的循环检测报错。

另外，你的逻辑本质是每次旋转一次链表（把尾节点移到头部），但没有考虑k远大于链表长度的情况，会做大量重复操作，效率极低且易出错。

修复后的代码 #

正确的思路是先计算链表长度，用k对长度取模减少重复操作，再找到分割点完成一次旋转即可：

# 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
        """
        # 处理边界情况
        if not head or not head.next or k == 0:
            return head
        
        # 计算链表长度，同时找到尾节点
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1
        
        # 取模，避免重复旋转整个链表
        k = k % length
        if k == 0:
            return head
        
        # 找到倒数第k+1个节点，作为分割点的前一个节点
        prev_node = head
        for _ in range(length - k - 1):
            prev_node = prev_node.next
        
        # 执行旋转操作
        new_head = prev_node.next
        prev_node.next = None  # 断开原链表连接
        tail.next = head       # 尾节点连原头节点
        
        return new_head

修复说明 #

1. 边界处理：空链表、单节点链表、k为0时直接返回原头，避免无效操作
2. 长度计算：统计链表长度，用k % length得到实际需要旋转的次数，避免重复旋转整个链表
3. 分割链表：找到分割点，断开原链表，将后半部分移到头部，全程不会形成循环
4. 高效操作：只遍历链表两次，时间复杂度O(n)，空间复杂度O(1)，符合题目要求

内容的提问来源于stack exchange，提问作者Nahi shady