You need to enable JavaScript to run this app. Python实现链表旋转k次:看不懂给定rotaten代码,求合规易懂解法
优惠活动
大模型
产品
解决方案
定价
更多

Python实现链表旋转k次:看不懂给定rotaten代码,求合规易懂解法

链表rotaten方法实现详解

核心逻辑

链表向右旋转k次的本质是:将链表末尾的k个节点截取出来,拼接至链表头部。由于旋转n次(n为链表总长度)和未旋转效果完全一致,因此无需处理所有k次旋转,只需先计算实际需要旋转的次数m = k % n,避免重复操作。
整个过程仅修改原有节点的next指针指向,不需要新建节点、不交换节点数据、也不会将链表转换为列表,完全符合题目约束。


实现步骤(完全匹配题目要求)

  1. 参数校验:首先判断传入的k是否小于0,若是直接抛出ValueError
  2. 边界情况处理:如果链表长度≤1(空链表或只有单个节点),旋转无意义,直接返回
  3. 计算实际旋转步数:m = k % self._size,若m == 0说明旋转后和原链表一致,直接返回
  4. 定位分割点:从原链表头节点出发,走self._size - m - 1步,到达「前半段链表的尾节点」(也就是分割位置)
  5. 指针重组拼接:
    • 保存分割点的下一个节点(即后半段链表的头节点)
    • 保存原链表的头、尾节点
    • 切断分割点和后半段的连接
    • 更新链表的头、尾指针为后半段的头、分割点
    • 将原链表尾的指针指向原链表头,完成拼接

完整可运行代码

class Node:
    def __init__(self, initdata):
        self._data = initdata
        self._next = None

    def get_data(self):
        return self._data

    def get_next(self):
        return self._next

    def set_data(self, newdata):
        self._data = newdata

    def set_next(self, newnext):
        self._next = newnext


class LinkedList:
    def __init__(self):
        # 补全原有参考代码缺失的初始化方法
        self._head = None  # 链表头节点
        self._last = None  # 链表尾节点
        self._size = 0     # 链表长度

    def add(self, item):
        # 尾插法辅助方法,方便测试
        temp = Node(item)
        if self._head is None:
            self._head = temp
            self._last = temp
        else:
            self._last.set_next(temp)
            self._last = temp
        self._size += 1

    def rotaten(self, k):
        # 1. 参数校验
        if k < 0:
            raise ValueError
        
        # 2. 边界情况:空链表/单节点链表无需旋转
        if self._size <= 1:
            return
        
        # 3. 计算实际需要旋转的次数,避免无效操作
        m = k % self._size
        if m == 0:
            return
        
        # 4. 定位分割点:前半段的尾节点,仅走对应步数,符合性能要求
        current = self._head
        for _ in range(self._size - m - 1):
            current = current.get_next()
        
        # 5. 保存关键节点指针
        chain_b = current.get_next()  # 后半段的头节点
        old_head = self._head         # 原链表头
        old_last = self._last         # 原链表尾

        # 6. 重组指针完成旋转
        current.set_next(None)        # 切断前半段和后半段的连接
        self._last = current          # 更新新的尾节点为分割点
        self._head = chain_b          # 更新新的头节点为后半段头
        old_last.set_next(old_head)    # 后半段尾接到原链表头

约束匹配说明

  • 性能符合要求:仅遍历size - m -1步,大O复杂度为O(n - m),和题目要求的O((n - k) % n)完全一致(常数项可忽略)
  • 未违反禁止约束:
    • 未循环调用旋转方法,仅做一次指针拼接
    • 未将链表转换为Python列表,全程操作链表节点
    • 未交换节点数据、未新建任何节点,仅修改原有节点的指针指向

测试示例

# 初始化链表 1->2->3->4->5
ll = LinkedList()
for i in [1,2,3,4,5]:
    ll.add(i)

# 向右旋转2次,预期结果为 4->5->1->2->3
ll.rotaten(2)
# 向右旋转7次(等价于旋转7%5=2次),结果和上面一致
ll.rotaten(7)
# 传入负数会抛出ValueError
try:
    ll.rotaten(-1)
except ValueError:
    print("参数校验生效")

内容的提问来源于stack exchange,提问作者V_20_sl

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.15 20:54:04