Python实现链表旋转k次:看不懂给定rotaten代码,求合规易懂解法
链表rotaten方法实现详解
核心逻辑
链表向右旋转k次的本质是:将链表末尾的k个节点截取出来,拼接至链表头部。由于旋转n次(n为链表总长度)和未旋转效果完全一致,因此无需处理所有k次旋转,只需先计算实际需要旋转的次数m = k % n,避免重复操作。
整个过程仅修改原有节点的next指针指向,不需要新建节点、不交换节点数据、也不会将链表转换为列表,完全符合题目约束。
实现步骤(完全匹配题目要求)
- 参数校验:首先判断传入的
k是否小于0,若是直接抛出ValueError - 边界情况处理:如果链表长度≤1(空链表或只有单个节点),旋转无意义,直接返回
- 计算实际旋转步数:
m = k % self._size,若m == 0说明旋转后和原链表一致,直接返回 - 定位分割点:从原链表头节点出发,走
self._size - m - 1步,到达「前半段链表的尾节点」(也就是分割位置) - 指针重组拼接:
- 保存分割点的下一个节点(即后半段链表的头节点)
- 保存原链表的头、尾节点
- 切断分割点和后半段的连接
- 更新链表的头、尾指针为后半段的头、分割点
- 将原链表尾的指针指向原链表头,完成拼接
完整可运行代码
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
相关产品推荐
相关产品推荐

