在很多算法训练手册里链表题往往被归为“入门容易精通难”的那一类。链表本身不复杂无非是节点结构和指针操作但一旦涉及边界条件、指针移动步数、循环与取模许多人就开始头大。LeetCode 61题“旋转链表”恰好就是这么一道题题干简明扼要说要给你一个链表的头节点旋转k次看着人畜无害可真要动手写代码时细节问题一个接一个。这篇文章我打算抛弃那种“先讲题意、再贴代码、最后总结复杂度”的流水账写法而是把我自己面对这道题时的完整思考过程、试错经历和最终沉淀下来的答题模板都写出来。无论你是刚接触链表的新手还是准备面试需要系统梳理的老手看这篇应该都有收获。1. 题目定位与核心难点拆解旋转链表Rotate List在LeetCode上的编号是61难度属于中等偏简单。题目描述大致是这样给定一个链表将链表每个节点向右移动k个位置。举个例子输入head [1,2,3,4,5]k 2 输出[4,5,1,2,3]输入head [0,1,2]k 4 输出[2,0,1]第一眼看上去这个问题和“旋转数组”很像但实际上链表和数组在数据结构本质上的差异导致这两道题的解法路径完全不同。1.1 理解“旋转”在链表中意味着什么在数组中做旋转通常可以用三次反转法或者用额外的空间拷贝切分后的部分。数组支持O(1)的随机访问所以无论怎么操作下标计算都很直接。链表则完全不同。链表节点只能通过next指针逐个向后访问不存在“直接用下标定位到某个节点”这种操作。所以旋转链表本质上做的是另一件事找到正确的断点位置把链表从这里切断然后把后半段拼接到前半段前面。也就是说“旋转k次”这个问题在链表场景下可以转换为“找到倒数第k个节点以此节点为新的链表头把前一段接到新链表的尾部”。这个理解非常关键。很多人在链表操作上卡壳往往就是没有在思维上完成这一步转换仍然试图逐个节点去“移动”它结果把问题做复杂了。1.2 头节点是定死的还是可以变的一个比较容易忽略的细节是这道题的结果中链表的“头节点”会发生变化。输入链表的头是1k2时输出链表的头变成了4。也就是说解题过程中我们不能默认head这个指针始终指向返回链表的头。需要有一个新的指针或者重新对head赋值来指向旋转后的新头部。这一点做算法题的时候很常见题目说“给你一个链表的头节点head”但这并不意味着最后返回的一定还是原来的head。对于链表结构发生变化的题目返回的结果往往是新的头节点或者是一些关键节点的指针。要有意识地区分“输入参数中的指针”和“最终返回的指针”。1.3 隐藏的数学问题k可能远大于链表长度再看题目给的约束条件。k的值可以非常大具体能大到什么程度取决于题目的边界设定。在很多版本的题目中k可以超过链表的长度甚至可能是0或者负数范围之外的超大整数。这里就要引出旋转链表最核心的一个数学处理取模。如果一个链表的长度是n那么旋转n次后链表会恢复到原始状态。所以实际有效的旋转次数是k % n而不是k本身。很多人第一次做这道题直接拿k去遍历链表结果链表都遍历到底了k还没用完造成了空指针异常。其实只需要取模一次问题就简化很多。注意取模的前提是n不为0。对于空链表head为None旋转多少次都是空链表直接返回head即可。这是边界条件的第一道坎。2. 思路推演从最朴素解法到最优解法接下来这个部分我会把几种解法的演进过程完整展现出来。面试中如果你能展现出这种递进思维会是很加分的亮点。因为面试官想看到的不是你直接背出最优解而是你理解每种方案背后的权衡。2.1 解法一朴素思路直接模拟旋转过程最直观、最暴力的方法就是每次旋转1位循环k次。旋转1位的操作是什么找到链表的尾节点把它摘下来放到头节点的位置。这个操作需要遍历一遍链表时间复杂度O(n)总共执行k次整体时间复杂度O(k * n)。这种解法的问题很明显当k很大时比如k超过10^9程序基本就跑不完了。每次旋转都要重复遍历链表浪费了大量时间。可以先用取模优化k k % n这样最多执行n次。即便如此最坏情况下的时间复杂度仍然是O(n^2)。对于链表长度较大或对性能有要求的场景这个方案不可行。不过模拟法也不是完全没有价值。它的代码写起来简单逻辑直观适合第一步先确认自己对“旋转”操作的理解是否正确。很多人在写其他高效解法之前都会先在脑子里过一遍这个模拟过程确保思路本身没有偏差。2.2 解法二快慢指针法快慢指针是链表题里非常经典的一种技巧用两个速度不同的指针遍历链表在特定条件满足时停下从而定位到目标节点。在旋转链表这道题里我们想要的其实是找到倒数第k个节点这个节点就是旋转后新链表的头节点。思路大致是这样先遍历一遍链表得到链表长度n。如果k大于n先取模k k % n。特判如果k为0说明旋转后链表不变直接返回head。用快指针fast先走k步。然后让慢指针slow和快指针fast一起走当fast走到链表末尾时slow正好指向倒数第k个节点即新链表的头节点的前驱节点。为什么快指针先走k步再一起走到末尾slow就停在目标位置这个逻辑可以这么理解快指针和慢指针之间的距离始终保持在k。当快指针到达链表的末尾节点时慢指针自然距离末尾还有k个节点也就是倒数第k1个节点。确切地说fast走到null时slow恰好指向倒数第k1个节点也就是新头节点的前驱。再往后挪一个节点就是倒数第k个节点。不过这里要小心有些讲解里说slow会指向倒数第k个节点实际上取决于fast停止时指向的是null还是最后一个节点。这在代码实现上会有细微差别后面我会在代码解析部分明确指出。2.3 解法三闭合为环一次定位第三种解法是我个人认为最优美也最推荐的先把链表闭合为一个环然后找到新的头部切开。具体步骤遍历链表统计节点个数n同时在遍历过程中把最后一个节点的next指向head形成一个环。对k取模k k % n。计算出新的头节点位置也就是链表中的第 n - k 个节点。从新头节点的前驱位置切开环设置新的尾节点的next为None返回新头节点。这种解法的时间复杂度是O(n)空间复杂度O(1)并且只遍历了一次链表如果遍历计数和闭合环同时完成的话。很多人在初次接触这个解法时最困惑的地方就是为什么新的头节点位置是第n - k个这个可以从两个方向理解。一种是数学推导向右旋转k次相当于把最后k个节点挪到最前面。所以新的头节点就是原来链表的第n - k个节点。另一种是从环的角度理解链表闭合成环后旋转k次本质上是在环上走了k步。如果从当前头节点出发往前走n - k步就会到达旋转后的新头节点位置。说到这儿有个很常见的误区要提醒一下不要直接从头节点开始找第n - k个节点因为在链表中找第n - k个节点需要n - k的步数这个步数计算如果粗心容易弄错索引。建议的方法是用一个指针从head开始移动移动到第n - k个节点的前驱位置然后执行切断操作。2.4 三种解法的对比与选型建议解法时间复杂度空间复杂度代码复杂度适用场景直接模拟O(k*n)O(1)低仅用于理解题意快慢指针O(n)O(1)中面试常规推荐闭合为环O(n)O(1)低笔试/实际编码最优如果是在面试现场我建议优先说快慢指针法因为它的思路更贴近“链表指针操作”的核心能力考察面试官容易在代码细节上追问。如果是自己在LeetCode上刷题或者时间有限想快速AC那就直接用闭合为环解法代码更简洁也更容易写对。3. 代码实现与关键细节逐行拆解既然已经梳理清楚思路这一节直接上代码。我会给出Python版本的闭合为环解法并逐段解释每一行的意图。之所以选Python是因为它在算法面试中用得最广泛代码表达力也最强。3.1 完整代码Python版本def rotateRight(head, k): # 处理空链表和单节点的特殊情况 if not head or not head.next: return head # 第一步遍历链表统计长度并记录尾节点 n 1 tail head while tail.next: tail tail.next n 1 # 第二步对k取模 k k % n if k 0: return head # 第三步闭合为环 tail.next head # 第四步找到新的头节点和新的尾节点 # 新尾节点是第 n - k 个节点新头节点是它的下一个节点 steps n - k new_tail head for _ in range(steps - 1): new_tail new_tail.next new_head new_tail.next new_tail.next None return new_head3.2 逐行解读避开常见的坑先看前面两个if判断if not head or not head.next。很多人在写这道题时只检查了not head忘了检查链表只有一个节点的情况。其实就算只有一个节点旋转多少次都还是它本身所以直接返回head也是对的。但这个边界如果漏了后面tail.next访问就会出问题。然后是统计链表长度的循环。这里的n初始值设为1tail初始指向head然后循环条件是while tail.next。这意味着当循环结束时tail就指向最后一个节点。整个循环跑完n就是链表长度。这个写法比较紧凑但有个隐含前提head不能为空所以前面那个空链表判断必须放在它之前。接下来是取模操作。k k % n的意思是实际需要旋转的次数是k对n取余。比如n5k7那么旋转7次和旋转2次效果相同。这里k % n等于2说明只需要把最后两个节点挪到前面。这里需要特别留意一种情况如果k取模之后等于0说明旋转n的整数倍次链表恢复原状直接返回head就行。不要小看这个判断它能避免后面无意义的操作还能防止一种特殊异常如果k是n的整数倍后面的steps会等于n进行for循环移动n-1步恰好会回到head自身也能正常工作。不过写上这个判断会让代码逻辑更清晰也更快。闭合为环的这行tail.next head是这道题的点睛之笔。它把链表变成了一个环形结构这样我们就可以放心地在环上移动指针而不必担心走到尽头出现None。真正容易出错的是最后的切断环节。steps n - k这个值表示从head出发要走多少步才能到达新的尾节点。很多人在这一步把索引搞混。我们推导一下旋转后链表新的头部是原来链表的第n - k个节点从1开始计数。例如链表[1,2,3,4,5]n5k2新的头部是4也就是第3个节点。等等这里似乎是第4个节点让我仔细算一下。嗯这里我重新推导一下避免前面这段误导人。对于[1,2,3,4,5]旋转2次的结果是[4,5,1,2,3]。新链表头是4在原链表中是第4个节点。n - k 5 - 2 3这对应的是第3个节点3也就是新链表的尾节点。所以更准确地表述是新链表的尾节点 原链表的第 n - k 个节点。新链表的头节点 原链表的第 n - k 1 个节点。我上面代码中的new_tail通过步数steps - 1 n - k - 1从head移动得到的就是第n - k个节点。举个例子n5k2steps 3从head第1个节点前进2步到达第3个节点值为3该节点确实是新链表的尾节点。验证通过。这里再提供一个生活化的类比假设你有一列火车车厢现在要把最后2节车厢挪到最前面。你需要先找到“第3节车厢”把它和它后面的车厢之间的连接断开再把最后2节车厢整体放到最前面。这里的第3节车厢就是新链表的尾节点。切断操作new_tail.next None这一步千万别漏它决定了新链表是一个单链表而不是继续带着尾巴环下去。如果漏掉LeetCode在输出时会进入死循环直接超时。3.3 快慢指针版本代码为了确保读者对另一种解法也有直观掌握我这里还是把快慢指针版本也写出来。虽然前面推荐了闭合为环解法但实际上快慢指针在面试中也是高频考点能做到两种解法都烂熟于心最好。def rotateRight(head, k): if not head or not head.next: return head # 统计链表长度 n 1 tail head while tail.next: tail tail.next n 1 k k % n if k 0: return head # 快指针先走k步 fast head slow head for _ in range(k): fast fast.next # 快慢指针一起走fast走到最后一个节点时 # slow指向倒数第k1个节点即新尾节点的前驱 while fast.next: fast fast.next slow slow.next # 此时slow指向新链表的尾节点slow.next是新头节点 new_head slow.next slow.next None # 原链表的尾节点接上原头节点 tail.next head return new_head对比可以发现闭合为环解法和快慢指针解法内部逻辑有相似之处但前者通过闭合环省去了快指针先走k步的操作代价是需要在切断时多移动n - k步。两者的总时间复杂度都是O(n)差别只在常数上。4. 复杂边界条件与高频踩坑点说实话这道题的解法本身不难难的是各种边界情况。我在初学时80%的错误都出在边界条件上。这里把常见的情况集中整理出来配上原因分析能帮大家节省大量debug时间。4.1 空链表传进来的head是None链表长度为0。此时无论k是多少返回结果都应该是None。如果不在代码开头处理后面所有操作都会因为访问None.next而抛出异常。4.2 单节点链表链表只有一个节点比如[1]无论k多大旋转结果都是[1]。在代码中体现为head.next为None可以提前返回head。但如果你的代码走完了整个流程也不会出错n1k%10直接返回head。所以这个特判不是必须的却能让意图更明确。4.3 k是链表长度的整数倍比如链表长度为5k10。这时旋转10次等价于旋转0次链表完全不变。如果不取模或者是取模后没有判断是否为0代码后续操作会得出错误的结果。因为k % n 0时按公式算出来的新头节点正好是原头节点但切断操作会把链表拆开导致返回了一个不完整的链表。所以在取模之后一定要对k0做判断直接返回head。这不仅是性能优化更是正确性保障。4.4 k非常巨大的情况题目输入范围里k可能是一个非常大的整数比如10^9甚至更大。如果不取模代码可能在k的循环中直接超时。正确的做法是一开始就取模这个操作可以把时间复杂度和输入的k值彻底解耦只与链表长度n有关。4.5 头节点变化的处理题目虽然给的是head但最终返回的可能是另外某个节点。在编码时不要受“输入变量名”的影响最终该返回什么就返回什么。闭合为环解法中返回的是new_head而不是head。有人习惯把new_head赋值给head再返回这在LeetCode的函数式编程风格中问题不大但最终return什么应该看的是“旋转后真正的头节点是谁”而不是变量名。5. 常见问题与实战排错经验这一节分享一些我在实际刷题和帮别人看代码过程中遇到的典型问题。如果你提交后出现了错误答案或者超时可以对照排查一下。5.1 死循环表现LeetCode评测返回Time Limit Exceeded代码在本地怎么跑都停不下来。原因闭合为环后新的链表尾部没有置为None链表仍然是环。比如[1,2,3]k1旋转后应该是[3,1,2]。如果你的代码里new_tail.next没有置为None那么遍历这个链表时就会从2跳到3再从3可能跳回前面的节点永远不会结束。排查方式检查切断操作new_tail.next None是否遗漏或者检查赋值顺序是否有误。5.2 结果元素顺序完全不对表现返回的链表长度没问题但元素顺序明显错误比如[1,2,3]旋转1次返回成了[2,3,1]。原因新头节点定位错误。多半是n - k的计算出了问题可能是索引从0开始还是从1开始没理清。一个靠谱的验证方法取一个长度为奇数的链表比如长度为5的链表k2手动演算一遍然后对照代码中的steps值。如果steps计算出来和手动推的不一致那一定是索引基准出了问题。5.3 忽略了k取模后的0值表现k是链表长度的整数倍时返回的链表比原链表少了几个节点。原因k % n等于0时新头节点应该是原head。但代码可能把new_tail定位到了链表最后一个节点之后或者把new_head指向了某个中间节点导致返回的链表被截断了。预防在取模之后立刻判断k是否为0。5.4 局部变量名混淆表现代码在本地测试正确一改变量名就报错。原因链表题中经常涉及多个指针比如tail、new_tail、new_head、slow、fast。新手最常犯的错误是在切断了new_tail.next之后又去访问原tail的next此时原链表已经被破坏了。经验之谈在需要保存旧信息时先存到变量里再操作。比如快慢指针解法中先保存tail head最后再通过tail.next head把环接起来。如果在移动指针过程中tail变量被覆盖那这个操作就找不到原尾节点了。5.5 单节点链表的处理不当表现head[1]k1正确输出应该是[1]但代码报错。原因忽略了对单节点链表的特判。虽然取模后k0可以直接返回但如果在取模之前就执行了while tail.nexttail.next为None循环条件不满足n1看起来也没问题。但有些人会先写if head.next is None: return head来判断单节点这个判断本身没问题但千万不要写成if head.next: return head这会漏掉值本身为0或False的节点。当然这里是链表节点对象不存在布尔值的问题但这个习惯在Python里很重要。6. 从这道题延伸出去的考点与思维模型一道题的价值不仅在于AC本身更在于它帮我们串联起了哪些知识点以及我们能否将其迁移到其他场景。旋转链表这道题背后藏着几个非常核心的链表思维模型。6.1 快慢指针的通用模型快慢指针并不仅仅用于找中点、判环。它还可以用于找链表的倒数第k个节点。判断链表是否有环。找到环的入口位置。判断回文链表。链表排序中的切分操作。如果你把“旋转链表”中的快慢指针用法吃透了你会发现“倒数第k个节点”这个变体在别的题目中反复出现。比如LeetCode 19题“删除链表的倒数第N个节点”思路几乎一样。6.2 闭合为环的思维迁移把一个单链表临时改造成环形结构解决完问题再切开这个技巧非常精妙也非常实用。它本质上是一种“先改结构再操作最后复原”的思路。类似的应用场景还包括循环链表的构造与遍历。约瑟夫环问题。数组旋转与链表旋转的对比学习。如果你在面试中提出了这种解法面试官大概率会追问“那如果链表非常大闭合为环会不会有什么问题”。这是一个加分机会你可以从空间复杂度和时间复杂度的角度回答闭合为环并没有引入额外的空间只是修改了原链表的结构。只要最后切开了就还是单链表不会造成内存泄漏问题。相比之下快慢指针解法则不修改原始链表结构在某些只读场景下更有优势。6.3 取模思想的普适性旋转类问题几乎都要用到取模。数组旋转、字符串循环位移、循环队列的队头队尾指针计算本质都在处理同一个数学问题如何把超过规模范围的循环操作缩小到有效范围内。在面试中如果你能主动想到取模并解释为什么面试官通常会认为你具备良好的数学敏感度。这一点在小公司笔试和大厂面试中都很加分。6.4 链表题通用调试策略链表题的调试比普通数组题要麻烦因为打印输出不方便。好在LeetCode有很好的可视化支持但本地调试时我习惯写一个简单的辅助函数来把链表转成列表。这样可以在每次操作前后打印观察结构变化是否符合预期。def linked_list_to_list(head): result [] while head: result.append(head.val) head head.next return result这个小工具在排查问题时极其好用。遇到不确定的情况打印一下当前链表的状态很快就能定位到哪一步出了问题。毕竟链表本身的节点跳转比较抽象肉眼很难跟上每一步的指针移动。7. 面试现场的表现建议与复盘总结最后聊聊面试中遇到这道题时怎么表现才能拿到更好的评价。这道题不算难但正因为它不难面试官反而更容易在细节上考察你的基本功。7.1 先和面试官确认边界动手写代码之前先说清楚你的假设链表是否可能为空k会不会是负数k的取值范围多大这些确认动作能在面试官心中建立“细心、有工程意识”的印象。虽然题目描述里通常会给出约束但主动问一遍并无坏处。7.2 明确空间复杂度这道题的空间复杂度是O(1)但有些面试官会特意问“如果你额外使用了O(n)的空间会怎么样”他们想考察的是你能否在不使用额外数组的情况下解决问题。所以面试时主动说明“我可以在O(1)空间内完成”会让你的答案更有竞争力。7.3 在白板/编辑器中的代码规范性链表题在白板上写代码时要格外注意指针操作的可读性。给每个指针命名时尽量体现它的角色比如new_tail就很直观。不要用一个temp到处接来接去那样别人看不懂你自己也容易出错。7.4 千万不要默写代码很多面经都会有这道题所以有些人会选择直接背答案。但如果面试官换一个提问方式比如“实现一个函数把链表循环右移k位”背代码的人很容易懵。更聪明的做法是理解旋转的本质是“找断点”然后无论怎么换包装你都能快速写出代码。做算法题最值得投资的不是记忆代码而是建立“问题转换”的思维模型。旋转链表这道题正确的思维路径是旋转k次 → 等价于把最后k个节点移到最前面 → 等价于找到第n-k个节点作为断点 → 切断并拼接。掌握了这条思维链换什么描述都不会怕。7.5 个人刷题时的顺序建议如果你刚开始接触链表类题目我建议按这个顺序练习反转链表LeetCode 206删除链表的倒数第N个节点LeetCode 19旋转链表LeetCode 61环形链表LeetCode 141、142回文链表LeetCode 234这五道题覆盖了链表操作中最核心的技能指针翻转、双指针定位、长度统计、环的判断与处理。把它们彻底吃透链表类题目的基础就非常扎实了。做完61题之后还可以做一道衍生题LeetCode 189“旋转数组”。对比两道题你会发现虽然数据结构不同但“取模 确定切分点”的思路是相通的。这种跨题型的对比总结是刷题水平提升最快的路径之一。我个人在实际刷题中体会最深的一点是链表题目最怕的不是逻辑复杂而是对自己写的代码“感觉对了”但一跑就错。归根结底还是在指针移动和边界条件上疏忽了。所以无论用哪种解法最后一定记得在本地跑几个边界case尤其是空链表、单节点、k等于0、k比链表长度大这四种情况。跑过这几组用例这道题才算真正过关。
在很多算法训练手册里链表题往往被归为“入门容易精通难”的那一类。链表本身不复杂无非是节点结构和指针操作但一旦涉及边界条件、指针移动步数、循环与取模许多人就开始头大。LeetCode 61题“旋转链表”恰好就是这么一道题题干简明扼要说要给你一个链表的头节点旋转k次看着人畜无害可真要动手写代码时细节问题一个接一个。这篇文章我打算抛弃那种“先讲题意、再贴代码、最后总结复杂度”的流水账写法而是把我自己面对这道题时的完整思考过程、试错经历和最终沉淀下来的答题模板都写出来。无论你是刚接触链表的新手还是准备面试需要系统梳理的老手看这篇应该都有收获。1. 题目定位与核心难点拆解旋转链表Rotate List在LeetCode上的编号是61难度属于中等偏简单。题目描述大致是这样给定一个链表将链表每个节点向右移动k个位置。举个例子输入head [1,2,3,4,5]k 2 输出[4,5,1,2,3]输入head [0,1,2]k 4 输出[2,0,1]第一眼看上去这个问题和“旋转数组”很像但实际上链表和数组在数据结构本质上的差异导致这两道题的解法路径完全不同。1.1 理解“旋转”在链表中意味着什么在数组中做旋转通常可以用三次反转法或者用额外的空间拷贝切分后的部分。数组支持O(1)的随机访问所以无论怎么操作下标计算都很直接。链表则完全不同。链表节点只能通过next指针逐个向后访问不存在“直接用下标定位到某个节点”这种操作。所以旋转链表本质上做的是另一件事找到正确的断点位置把链表从这里切断然后把后半段拼接到前半段前面。也就是说“旋转k次”这个问题在链表场景下可以转换为“找到倒数第k个节点以此节点为新的链表头把前一段接到新链表的尾部”。这个理解非常关键。很多人在链表操作上卡壳往往就是没有在思维上完成这一步转换仍然试图逐个节点去“移动”它结果把问题做复杂了。1.2 头节点是定死的还是可以变的一个比较容易忽略的细节是这道题的结果中链表的“头节点”会发生变化。输入链表的头是1k2时输出链表的头变成了4。也就是说解题过程中我们不能默认head这个指针始终指向返回链表的头。需要有一个新的指针或者重新对head赋值来指向旋转后的新头部。这一点做算法题的时候很常见题目说“给你一个链表的头节点head”但这并不意味着最后返回的一定还是原来的head。对于链表结构发生变化的题目返回的结果往往是新的头节点或者是一些关键节点的指针。要有意识地区分“输入参数中的指针”和“最终返回的指针”。1.3 隐藏的数学问题k可能远大于链表长度再看题目给的约束条件。k的值可以非常大具体能大到什么程度取决于题目的边界设定。在很多版本的题目中k可以超过链表的长度甚至可能是0或者负数范围之外的超大整数。这里就要引出旋转链表最核心的一个数学处理取模。如果一个链表的长度是n那么旋转n次后链表会恢复到原始状态。所以实际有效的旋转次数是k % n而不是k本身。很多人第一次做这道题直接拿k去遍历链表结果链表都遍历到底了k还没用完造成了空指针异常。其实只需要取模一次问题就简化很多。注意取模的前提是n不为0。对于空链表head为None旋转多少次都是空链表直接返回head即可。这是边界条件的第一道坎。2. 思路推演从最朴素解法到最优解法接下来这个部分我会把几种解法的演进过程完整展现出来。面试中如果你能展现出这种递进思维会是很加分的亮点。因为面试官想看到的不是你直接背出最优解而是你理解每种方案背后的权衡。2.1 解法一朴素思路直接模拟旋转过程最直观、最暴力的方法就是每次旋转1位循环k次。旋转1位的操作是什么找到链表的尾节点把它摘下来放到头节点的位置。这个操作需要遍历一遍链表时间复杂度O(n)总共执行k次整体时间复杂度O(k * n)。这种解法的问题很明显当k很大时比如k超过10^9程序基本就跑不完了。每次旋转都要重复遍历链表浪费了大量时间。可以先用取模优化k k % n这样最多执行n次。即便如此最坏情况下的时间复杂度仍然是O(n^2)。对于链表长度较大或对性能有要求的场景这个方案不可行。不过模拟法也不是完全没有价值。它的代码写起来简单逻辑直观适合第一步先确认自己对“旋转”操作的理解是否正确。很多人在写其他高效解法之前都会先在脑子里过一遍这个模拟过程确保思路本身没有偏差。2.2 解法二快慢指针法快慢指针是链表题里非常经典的一种技巧用两个速度不同的指针遍历链表在特定条件满足时停下从而定位到目标节点。在旋转链表这道题里我们想要的其实是找到倒数第k个节点这个节点就是旋转后新链表的头节点。思路大致是这样先遍历一遍链表得到链表长度n。如果k大于n先取模k k % n。特判如果k为0说明旋转后链表不变直接返回head。用快指针fast先走k步。然后让慢指针slow和快指针fast一起走当fast走到链表末尾时slow正好指向倒数第k个节点即新链表的头节点的前驱节点。为什么快指针先走k步再一起走到末尾slow就停在目标位置这个逻辑可以这么理解快指针和慢指针之间的距离始终保持在k。当快指针到达链表的末尾节点时慢指针自然距离末尾还有k个节点也就是倒数第k1个节点。确切地说fast走到null时slow恰好指向倒数第k1个节点也就是新头节点的前驱。再往后挪一个节点就是倒数第k个节点。不过这里要小心有些讲解里说slow会指向倒数第k个节点实际上取决于fast停止时指向的是null还是最后一个节点。这在代码实现上会有细微差别后面我会在代码解析部分明确指出。2.3 解法三闭合为环一次定位第三种解法是我个人认为最优美也最推荐的先把链表闭合为一个环然后找到新的头部切开。具体步骤遍历链表统计节点个数n同时在遍历过程中把最后一个节点的next指向head形成一个环。对k取模k k % n。计算出新的头节点位置也就是链表中的第 n - k 个节点。从新头节点的前驱位置切开环设置新的尾节点的next为None返回新头节点。这种解法的时间复杂度是O(n)空间复杂度O(1)并且只遍历了一次链表如果遍历计数和闭合环同时完成的话。很多人在初次接触这个解法时最困惑的地方就是为什么新的头节点位置是第n - k个这个可以从两个方向理解。一种是数学推导向右旋转k次相当于把最后k个节点挪到最前面。所以新的头节点就是原来链表的第n - k个节点。另一种是从环的角度理解链表闭合成环后旋转k次本质上是在环上走了k步。如果从当前头节点出发往前走n - k步就会到达旋转后的新头节点位置。说到这儿有个很常见的误区要提醒一下不要直接从头节点开始找第n - k个节点因为在链表中找第n - k个节点需要n - k的步数这个步数计算如果粗心容易弄错索引。建议的方法是用一个指针从head开始移动移动到第n - k个节点的前驱位置然后执行切断操作。2.4 三种解法的对比与选型建议解法时间复杂度空间复杂度代码复杂度适用场景直接模拟O(k*n)O(1)低仅用于理解题意快慢指针O(n)O(1)中面试常规推荐闭合为环O(n)O(1)低笔试/实际编码最优如果是在面试现场我建议优先说快慢指针法因为它的思路更贴近“链表指针操作”的核心能力考察面试官容易在代码细节上追问。如果是自己在LeetCode上刷题或者时间有限想快速AC那就直接用闭合为环解法代码更简洁也更容易写对。3. 代码实现与关键细节逐行拆解既然已经梳理清楚思路这一节直接上代码。我会给出Python版本的闭合为环解法并逐段解释每一行的意图。之所以选Python是因为它在算法面试中用得最广泛代码表达力也最强。3.1 完整代码Python版本def rotateRight(head, k): # 处理空链表和单节点的特殊情况 if not head or not head.next: return head # 第一步遍历链表统计长度并记录尾节点 n 1 tail head while tail.next: tail tail.next n 1 # 第二步对k取模 k k % n if k 0: return head # 第三步闭合为环 tail.next head # 第四步找到新的头节点和新的尾节点 # 新尾节点是第 n - k 个节点新头节点是它的下一个节点 steps n - k new_tail head for _ in range(steps - 1): new_tail new_tail.next new_head new_tail.next new_tail.next None return new_head3.2 逐行解读避开常见的坑先看前面两个if判断if not head or not head.next。很多人在写这道题时只检查了not head忘了检查链表只有一个节点的情况。其实就算只有一个节点旋转多少次都还是它本身所以直接返回head也是对的。但这个边界如果漏了后面tail.next访问就会出问题。然后是统计链表长度的循环。这里的n初始值设为1tail初始指向head然后循环条件是while tail.next。这意味着当循环结束时tail就指向最后一个节点。整个循环跑完n就是链表长度。这个写法比较紧凑但有个隐含前提head不能为空所以前面那个空链表判断必须放在它之前。接下来是取模操作。k k % n的意思是实际需要旋转的次数是k对n取余。比如n5k7那么旋转7次和旋转2次效果相同。这里k % n等于2说明只需要把最后两个节点挪到前面。这里需要特别留意一种情况如果k取模之后等于0说明旋转n的整数倍次链表恢复原状直接返回head就行。不要小看这个判断它能避免后面无意义的操作还能防止一种特殊异常如果k是n的整数倍后面的steps会等于n进行for循环移动n-1步恰好会回到head自身也能正常工作。不过写上这个判断会让代码逻辑更清晰也更快。闭合为环的这行tail.next head是这道题的点睛之笔。它把链表变成了一个环形结构这样我们就可以放心地在环上移动指针而不必担心走到尽头出现None。真正容易出错的是最后的切断环节。steps n - k这个值表示从head出发要走多少步才能到达新的尾节点。很多人在这一步把索引搞混。我们推导一下旋转后链表新的头部是原来链表的第n - k个节点从1开始计数。例如链表[1,2,3,4,5]n5k2新的头部是4也就是第3个节点。等等这里似乎是第4个节点让我仔细算一下。嗯这里我重新推导一下避免前面这段误导人。对于[1,2,3,4,5]旋转2次的结果是[4,5,1,2,3]。新链表头是4在原链表中是第4个节点。n - k 5 - 2 3这对应的是第3个节点3也就是新链表的尾节点。所以更准确地表述是新链表的尾节点 原链表的第 n - k 个节点。新链表的头节点 原链表的第 n - k 1 个节点。我上面代码中的new_tail通过步数steps - 1 n - k - 1从head移动得到的就是第n - k个节点。举个例子n5k2steps 3从head第1个节点前进2步到达第3个节点值为3该节点确实是新链表的尾节点。验证通过。这里再提供一个生活化的类比假设你有一列火车车厢现在要把最后2节车厢挪到最前面。你需要先找到“第3节车厢”把它和它后面的车厢之间的连接断开再把最后2节车厢整体放到最前面。这里的第3节车厢就是新链表的尾节点。切断操作new_tail.next None这一步千万别漏它决定了新链表是一个单链表而不是继续带着尾巴环下去。如果漏掉LeetCode在输出时会进入死循环直接超时。3.3 快慢指针版本代码为了确保读者对另一种解法也有直观掌握我这里还是把快慢指针版本也写出来。虽然前面推荐了闭合为环解法但实际上快慢指针在面试中也是高频考点能做到两种解法都烂熟于心最好。def rotateRight(head, k): if not head or not head.next: return head # 统计链表长度 n 1 tail head while tail.next: tail tail.next n 1 k k % n if k 0: return head # 快指针先走k步 fast head slow head for _ in range(k): fast fast.next # 快慢指针一起走fast走到最后一个节点时 # slow指向倒数第k1个节点即新尾节点的前驱 while fast.next: fast fast.next slow slow.next # 此时slow指向新链表的尾节点slow.next是新头节点 new_head slow.next slow.next None # 原链表的尾节点接上原头节点 tail.next head return new_head对比可以发现闭合为环解法和快慢指针解法内部逻辑有相似之处但前者通过闭合环省去了快指针先走k步的操作代价是需要在切断时多移动n - k步。两者的总时间复杂度都是O(n)差别只在常数上。4. 复杂边界条件与高频踩坑点说实话这道题的解法本身不难难的是各种边界情况。我在初学时80%的错误都出在边界条件上。这里把常见的情况集中整理出来配上原因分析能帮大家节省大量debug时间。4.1 空链表传进来的head是None链表长度为0。此时无论k是多少返回结果都应该是None。如果不在代码开头处理后面所有操作都会因为访问None.next而抛出异常。4.2 单节点链表链表只有一个节点比如[1]无论k多大旋转结果都是[1]。在代码中体现为head.next为None可以提前返回head。但如果你的代码走完了整个流程也不会出错n1k%10直接返回head。所以这个特判不是必须的却能让意图更明确。4.3 k是链表长度的整数倍比如链表长度为5k10。这时旋转10次等价于旋转0次链表完全不变。如果不取模或者是取模后没有判断是否为0代码后续操作会得出错误的结果。因为k % n 0时按公式算出来的新头节点正好是原头节点但切断操作会把链表拆开导致返回了一个不完整的链表。所以在取模之后一定要对k0做判断直接返回head。这不仅是性能优化更是正确性保障。4.4 k非常巨大的情况题目输入范围里k可能是一个非常大的整数比如10^9甚至更大。如果不取模代码可能在k的循环中直接超时。正确的做法是一开始就取模这个操作可以把时间复杂度和输入的k值彻底解耦只与链表长度n有关。4.5 头节点变化的处理题目虽然给的是head但最终返回的可能是另外某个节点。在编码时不要受“输入变量名”的影响最终该返回什么就返回什么。闭合为环解法中返回的是new_head而不是head。有人习惯把new_head赋值给head再返回这在LeetCode的函数式编程风格中问题不大但最终return什么应该看的是“旋转后真正的头节点是谁”而不是变量名。5. 常见问题与实战排错经验这一节分享一些我在实际刷题和帮别人看代码过程中遇到的典型问题。如果你提交后出现了错误答案或者超时可以对照排查一下。5.1 死循环表现LeetCode评测返回Time Limit Exceeded代码在本地怎么跑都停不下来。原因闭合为环后新的链表尾部没有置为None链表仍然是环。比如[1,2,3]k1旋转后应该是[3,1,2]。如果你的代码里new_tail.next没有置为None那么遍历这个链表时就会从2跳到3再从3可能跳回前面的节点永远不会结束。排查方式检查切断操作new_tail.next None是否遗漏或者检查赋值顺序是否有误。5.2 结果元素顺序完全不对表现返回的链表长度没问题但元素顺序明显错误比如[1,2,3]旋转1次返回成了[2,3,1]。原因新头节点定位错误。多半是n - k的计算出了问题可能是索引从0开始还是从1开始没理清。一个靠谱的验证方法取一个长度为奇数的链表比如长度为5的链表k2手动演算一遍然后对照代码中的steps值。如果steps计算出来和手动推的不一致那一定是索引基准出了问题。5.3 忽略了k取模后的0值表现k是链表长度的整数倍时返回的链表比原链表少了几个节点。原因k % n等于0时新头节点应该是原head。但代码可能把new_tail定位到了链表最后一个节点之后或者把new_head指向了某个中间节点导致返回的链表被截断了。预防在取模之后立刻判断k是否为0。5.4 局部变量名混淆表现代码在本地测试正确一改变量名就报错。原因链表题中经常涉及多个指针比如tail、new_tail、new_head、slow、fast。新手最常犯的错误是在切断了new_tail.next之后又去访问原tail的next此时原链表已经被破坏了。经验之谈在需要保存旧信息时先存到变量里再操作。比如快慢指针解法中先保存tail head最后再通过tail.next head把环接起来。如果在移动指针过程中tail变量被覆盖那这个操作就找不到原尾节点了。5.5 单节点链表的处理不当表现head[1]k1正确输出应该是[1]但代码报错。原因忽略了对单节点链表的特判。虽然取模后k0可以直接返回但如果在取模之前就执行了while tail.nexttail.next为None循环条件不满足n1看起来也没问题。但有些人会先写if head.next is None: return head来判断单节点这个判断本身没问题但千万不要写成if head.next: return head这会漏掉值本身为0或False的节点。当然这里是链表节点对象不存在布尔值的问题但这个习惯在Python里很重要。6. 从这道题延伸出去的考点与思维模型一道题的价值不仅在于AC本身更在于它帮我们串联起了哪些知识点以及我们能否将其迁移到其他场景。旋转链表这道题背后藏着几个非常核心的链表思维模型。6.1 快慢指针的通用模型快慢指针并不仅仅用于找中点、判环。它还可以用于找链表的倒数第k个节点。判断链表是否有环。找到环的入口位置。判断回文链表。链表排序中的切分操作。如果你把“旋转链表”中的快慢指针用法吃透了你会发现“倒数第k个节点”这个变体在别的题目中反复出现。比如LeetCode 19题“删除链表的倒数第N个节点”思路几乎一样。6.2 闭合为环的思维迁移把一个单链表临时改造成环形结构解决完问题再切开这个技巧非常精妙也非常实用。它本质上是一种“先改结构再操作最后复原”的思路。类似的应用场景还包括循环链表的构造与遍历。约瑟夫环问题。数组旋转与链表旋转的对比学习。如果你在面试中提出了这种解法面试官大概率会追问“那如果链表非常大闭合为环会不会有什么问题”。这是一个加分机会你可以从空间复杂度和时间复杂度的角度回答闭合为环并没有引入额外的空间只是修改了原链表的结构。只要最后切开了就还是单链表不会造成内存泄漏问题。相比之下快慢指针解法则不修改原始链表结构在某些只读场景下更有优势。6.3 取模思想的普适性旋转类问题几乎都要用到取模。数组旋转、字符串循环位移、循环队列的队头队尾指针计算本质都在处理同一个数学问题如何把超过规模范围的循环操作缩小到有效范围内。在面试中如果你能主动想到取模并解释为什么面试官通常会认为你具备良好的数学敏感度。这一点在小公司笔试和大厂面试中都很加分。6.4 链表题通用调试策略链表题的调试比普通数组题要麻烦因为打印输出不方便。好在LeetCode有很好的可视化支持但本地调试时我习惯写一个简单的辅助函数来把链表转成列表。这样可以在每次操作前后打印观察结构变化是否符合预期。def linked_list_to_list(head): result [] while head: result.append(head.val) head head.next return result这个小工具在排查问题时极其好用。遇到不确定的情况打印一下当前链表的状态很快就能定位到哪一步出了问题。毕竟链表本身的节点跳转比较抽象肉眼很难跟上每一步的指针移动。7. 面试现场的表现建议与复盘总结最后聊聊面试中遇到这道题时怎么表现才能拿到更好的评价。这道题不算难但正因为它不难面试官反而更容易在细节上考察你的基本功。7.1 先和面试官确认边界动手写代码之前先说清楚你的假设链表是否可能为空k会不会是负数k的取值范围多大这些确认动作能在面试官心中建立“细心、有工程意识”的印象。虽然题目描述里通常会给出约束但主动问一遍并无坏处。7.2 明确空间复杂度这道题的空间复杂度是O(1)但有些面试官会特意问“如果你额外使用了O(n)的空间会怎么样”他们想考察的是你能否在不使用额外数组的情况下解决问题。所以面试时主动说明“我可以在O(1)空间内完成”会让你的答案更有竞争力。7.3 在白板/编辑器中的代码规范性链表题在白板上写代码时要格外注意指针操作的可读性。给每个指针命名时尽量体现它的角色比如new_tail就很直观。不要用一个temp到处接来接去那样别人看不懂你自己也容易出错。7.4 千万不要默写代码很多面经都会有这道题所以有些人会选择直接背答案。但如果面试官换一个提问方式比如“实现一个函数把链表循环右移k位”背代码的人很容易懵。更聪明的做法是理解旋转的本质是“找断点”然后无论怎么换包装你都能快速写出代码。做算法题最值得投资的不是记忆代码而是建立“问题转换”的思维模型。旋转链表这道题正确的思维路径是旋转k次 → 等价于把最后k个节点移到最前面 → 等价于找到第n-k个节点作为断点 → 切断并拼接。掌握了这条思维链换什么描述都不会怕。7.5 个人刷题时的顺序建议如果你刚开始接触链表类题目我建议按这个顺序练习反转链表LeetCode 206删除链表的倒数第N个节点LeetCode 19旋转链表LeetCode 61环形链表LeetCode 141、142回文链表LeetCode 234这五道题覆盖了链表操作中最核心的技能指针翻转、双指针定位、长度统计、环的判断与处理。把它们彻底吃透链表类题目的基础就非常扎实了。做完61题之后还可以做一道衍生题LeetCode 189“旋转数组”。对比两道题你会发现虽然数据结构不同但“取模 确定切分点”的思路是相通的。这种跨题型的对比总结是刷题水平提升最快的路径之一。我个人在实际刷题中体会最深的一点是链表题目最怕的不是逻辑复杂而是对自己写的代码“感觉对了”但一跑就错。归根结底还是在指针移动和边界条件上疏忽了。所以无论用哪种解法最后一定记得在本地跑几个边界case尤其是空链表、单节点、k等于0、k比链表长度大这四种情况。跑过这几组用例这道题才算真正过关。
