先说个有趣的事很多刷题群的同学会把标题记成“Leetcode 107 旋转链表”然后兴冲冲打开题库发现 107 题其实是二叉树的层序遍历 II。真正讲“旋转链表”的是 LeetCode 61。题号串了但知识点不串——旋转链表是链表操作里非常经典的一类题面试出现的频率不低而且它把“找断点”“处理循环”“边界条件”这几个基本功全揉在一起了。这篇文章我按“旋转链表”这个核心主题来写题号乌龙顺便帮你避了重点是把这个题的思路、代码、坑一次讲透。适合谁看如果你正在准备算法面试链表题刷到中等难度就卡住或者你做过这题但总是边界出错再或者你只是想弄明白“为什么有人能把链表题写得那么干净”——这篇文章都适合。我会把从题目理解到代码落地的完整过程拆开先讲清楚题目在考什么再给两种主流解法然后逐步调一遍边界条件最后把我自己踩过的坑和排查思路整理成速查表。你可以直接照着复现也可以拿去做面试前的专项复习。1. 题目到底在考什么先看清旋转的本质1.1 从题号乌龙说到题目原文先把题号说清楚。LeetCode 107 是“二叉树的层序遍历 II”跟链表没关系。旋转链表在 LeetCode 上是第 61 题题目原文大致是给你一个链表的头节点 head旋转链表将链表每个节点向右移动 k 个位置。举个例子输入head [1,2,3,4,5]k 2输出[4,5,1,2,3]输入head [1,2,3]k 4输出[2,3,1]为什么这么容易记混因为很多人的笔记本上写着“Leetcode 107 旋转链表”可能是从旧版题库、纸质笔记或者视频课程的章节编号里抄来的。刷题的时候标题党没关系但你要知道面试时你不可能跟面试官说“我做的那个题号是 107”你得清楚题目本身。这里我建议你直接按“旋转链表”这个关键词去搜题目不要死记题号。题目原文里有两个容易忽略的细节。第一k 可能很大可能超过链表长度所以必须先取模。第二题目说的是“向右移动”不是“向左移动”。向右移动 k 个位置本质上就是让链表从倒数第 k 个节点处断开把后半段搬到前面。这两个细节不抓死后面写代码必出问题。1.2 旋转的含义与“边界感”“向右旋转”这个动作用日常例子类比就像是把一串项链的某个位置切开把末尾那一截提到开头。链表没有随机访问你没法像数组那样直接通过下标定位必须一个节点一个节点走。这也是链表题的通用难点所有操作都只能靠指针遍历完成。数组旋转可以这样做# 数组版本便于理解“旋转”语义 def rotate_array(nums, k): k % len(nums) nums[:] nums[-k:] nums[:-k] # 后半段拼到前面链表没有切片所以你只能手动找到那个“断开点”。因此这个题的真正考点不是旋转本身而是能不能想到先求链表长度能不能正确处理 k 对长度取模能不能准确找到新的头节点和新的尾节点能不能把尾节点和原头节点接上同时把新尾节点的 next 置空。这四个点每一个都不难但合在一起就非常容易写出“跑测试用例对了一提交就超时或者报错”的代码。说白了这题考的就是对链表指针操作的“边界感”。边界感这个词听起来玄实际上就是你脑子里得时刻清楚当前指针指向谁谁还指着它谁需要被改成 null。2. 核心思路拆解两种主流解法与选型逻辑2.1 最直觉的解法先断开再拼接最容易想到的做法是分三步第一步遍历一遍链表求出长度 n第二步k k % n第三步找到倒数第 k 个节点的前一个节点把后半段切下来接到链表头部。听起来很简单但实现时很多人的代码会啰嗦比如定义四五个指针dummyHead、slow、fast、prev、tail……其实核心只需要三个指针一个指向原尾节点一个指向新尾节点一个指向新头节点。如果链表是 1 - 2 - 3 - 4 - 5k 2那么原尾节点是 5新尾节点是 3因为倒数第 2 个节点的前一个是 3新头节点是 4最终连接方式是 4 - 5 - 1 - 2 - 3。关键操作是tail.next head; // 原尾接原头形成环 prev.next null; // 新尾断开 head newHead; // 新头成为链表头这种解法的优势是逻辑直白代码一读就懂。劣势是你可能需要两遍遍历一遍求长度一遍找断点。但两遍遍历在链表题里完全可接受时间复杂度仍然是 O(n)。2.2 更优雅的做法连成环再断开如果你觉得“找倒数第 k 个节点的前一个节点”这个说法每次都要想半天那可以用第二种做法先把链表连成环再在合适的位置断开。步骤是这样的遍历链表求出长度 n同时让尾节点的 next 指向 head形成环计算需要移动的步数 move n - k % n从原头节点出发走 move 步新的头节点就在这个位置把断点前的节点的 next 置为 null。为什么用 n - k % n 而不是直接用 k因为“向右移动 k 个位置”等效于“从头部向左移动 n - k 个位置”。你可以拿一个长度为 5 的链表k2 来验证向右移动 2 位新头是 4从头开始数4 是第 4 个节点而 n - k 3意味着从原头节点出发走 3 步索引从 0 开始正好到达 4。这个方法刚接触时可能觉得绕但它有个巨大的好处你不需要再单独找“倒数第 k 个节点的前一个节点”只需要记住“走几步后正好落在新头节点”。我当时学的时候觉得这个思路像魔术一样但后来想通了向右旋转的本质就是把链表从某个位置截断而截断位置可以通过取模和减法统一计算。2.3 两种思路怎么选两者时间复杂度一样空间复杂度都是 O(1)。区别主要在代码风格和出错概率上。如果你对“倒数第 k 个节点”这类描述特别敏感推荐第一种因为它更贴合直觉面试时解释起来也顺畅。如果你希望代码尽量短、逻辑尽量统一推荐第二种因为它天然把求长度、找断点、处理 k 大于长度这三种情况都覆盖了。我自己在实际刷题时两种都写过。第一版用“断开再拼接”代码 30 行左右后来觉得每次都要小心处理 head、tail、newHead、newTail 四个变量容易写岔改成了“连成环再断开”代码量减少而且很少出边界错误。现在我的默认模板就是第二种简单可靠。3. 手写实现与逐步调试3.1 C 实现教科书版我先把 C 版本写出来这个版本用的是“连成环再断开”的思路。你直接照着敲一遍然后把注释挡住自己写一遍效果比纯看要好得多。class Solution { public: ListNode* rotateRight(ListNode* head, int k) { // 空链表或只有一个节点旋转无意义 if (head nullptr || head-next nullptr) { return head; } // 第一遍遍历求长度并让尾节点指向头节点 int n 1; ListNode* tail head; while (tail-next ! nullptr) { tail tail-next; n; } tail-next head; // 形成环 // 计算新的头节点位置 int move n - k % n; // 从原头节点出发走 move 步 ListNode* newTail head; while (--move) { newTail newTail-next; } ListNode* newHead newTail-next; // 断开环 newTail-next nullptr; return newHead; } };这段代码里最容易被问到的两个点第一为什么n的初始值是 1 而不是 0因为当前已经有一个节点了循环条件是tail-next ! nullptr所以当链表长度为 5 时循环会执行 4 次n最终为 5。第二为什么while (--move)而不是while (move--)因为move表示从原头节点开始要走多少条边才能到达新头节点。假设新头是原链表的第 4 个节点从头节点出发需要经过 3 条边。初始时newTail指向头节点已经在第 0 个位置所以走 3 条边循环应该执行 3 次。while (--move)是先减再判断第一次判断时 move 已经变成 n - k % n - 1所以总共执行 move 初始值减 1 次。如果写成while (move--)就会多走一步直接到新头节点的下一个节点了bug 就出来了。这个问题我在面试辅导时反复强调过几乎每次都有同学踩中。3.2 Python 实现精简版Python 的写法逻辑一样只是语法上更简洁。这里我顺手加了一些打印语句方便你调试时看指针变化。class Solution: def rotateRight(self, head: Optional[ListNode], k: int) - Optional[ListNode]: if not head or not head.next: return head # 求长度并形成环 n 1 tail head while tail.next: tail tail.next n 1 tail.next head # 计算新头位置 move n - k % n # 找到新尾节点 new_tail head for _ in range(move - 1): new_tail new_tail.next new_head new_tail.next new_tail.next None return new_head这里for _ in range(move - 1)和 C 里的while (--move)是等价的。如果你用range(move)结果就是多走一步会让整个链表少一个节点调试时输出结果会非常诡异。我建议你调试时这样写def rotateRight(self, head, k): if not head or not head.next: return head n 1 tail head while tail.next: tail tail.next n 1 print(原来长度:, n, 尾节点值:, tail.val) tail.next head move n - k % n print(需要走几步:, move) new_tail head for _ in range(move - 1): new_tail new_tail.next print(新尾节点值:, new_tail.val) new_head new_tail.next new_tail.next None return new_head用[1,2,3,4,5]k2 测试输出会是这样原来长度: 5 尾节点值: 5 需要走几步: 3 新尾节点值: 3然后返回的链表就是[4,5,1,2,3]。把这个过程打印出来以后你就不会再对move的算法产生怀疑了。3.3 边界条件逐条过面试官最喜欢问的就是边界条件。这个题的边界条件有四个我一条条说链表为空head None直接返回空。链表只有一个节点旋转多少次都是它自己直接返回。k 为 0无论链表多长直接返回原链表。k % n为 0move n - 0 n走 n 步后回到原头节点代码也能正确处理但提前判断可以减少操作。k 远大于 n比如 n3k100必须先取模。如果不取模move n - k % n会变成3 - 100 % 3 3 - 1 2正确如果忘了取模直接n - k -97然后while (--move)就会死循环或者崩溃。这是这个题最容易翻车的点。我建议在代码开头多写一条if (k 0) { return head; }这不是必须的因为后面的逻辑能兜住但写出来一方面是语义清晰另一方面面试官会觉得你边界意识强。4. 面试官真正想看到的点4.1 时间复杂度与空间复杂度这个题的标准答案是 O(n) 时间O(1) 空间。很多同学只背结论但面试官一般会追问一句“为什么是 O(n)”你要能说清楚第一遍遍历求长度是 O(n)第二遍找断点最多也是 O(n)不管 k 多大取模后最多移动 n 次所以整体是 O(n)。整个过程没有使用额外数据结构所以空间复杂度是 O(1)。“空间复杂度 O(1)”这个说法在链表题里尤其重要因为很多数组题的空间复杂度可以 O(n)链表题如果用了额外数组面试官会皱眉头。我见过有人用数组存下所有节点值旋转后再重建链表虽然跑得过但面试时会被追问“能不能优化”本质上是没掌握链表操作。如果你能直接写出指针操作版本已经和“会用数组偷懒”的候选人拉开差距了。4.2 一题多解与升级考法这个题最经典的变形是“求第 k 个节点”、“删除倒数第 n 个节点”、“合并 K 个有序链表”。它们都在考同一个能力快慢指针和链表断点处理。如果你把旋转链表写熟了再去看“删除链表的倒数第 N 个节点”思路几乎是平移的——都是先求长度或者用快慢指针找位置。再看“链表是不是回文结构”也是先找到中点再反转后半段。链表题就是这样题型看着多核心手法就是遍历、断开、重连、反转。面试官如果觉得这题你答得太顺利可能会加一个限制要求不能先求链表长度也就是传说中的“一次遍历完成旋转”。这种情况下快慢指针登场快指针先走 k % n 步然后快慢指针一起走快指针到达尾节点时慢指针正好停在新尾节点。但这里有个前提你依然需要知道至少一个完整环的长度才能取模所以“完全不知道长度”其实做不到。面试官说“不能先求长度”时通常意思是“能不能不要第一轮单独遍历”你可以解释因为 k 可能大于长度必须先求长度取模否则无法确定边界。如果你这么回答面试官反而会觉得你考虑周全。4.3 代码风格和命名习惯很多人忽略了一点面试时代码的可读性比“跑通”更重要。变量名写t1、t2、t3面试官很难跟上你的思路写tail、newTail、newHead即使有小瑕疵面试官也更容易理解你的意图。我建议你写完代码后大声把注释读一遍看能不能像讲故事一样讲通顺。比如我先求长度并让尾节点指向头节点我计算需要走几步我找到新尾和新头我断开环。如果这四句话你都能对应到代码行那这道题就真的吃透了。我面试别人的时候其实不太在意候选人是否一次写对更在意他在叙述思路时是否清晰。能把自己代码讲清楚的人通常边界意识也不会差。5. 常见问题与排查技巧实录5.1 错误一k 取模前就开始移动这是我见过最多的问题。有人一上来就写for i in range(k)结果 k 是 1000000链表长度只有 5直接死循环或者超时。正确的做法是在任何指针移动之前先求出链表长度然后k % n。这里有个心理层面的原因题目描述里写的 k 通常很小比如 2、3人脑会下意识觉得 k 不需要特殊处理。但测试用例里一定会有一个大数。所以拿题第一步不要急着看示例先看数据范围。链表题的范围一般不写但你要默认 k 可能超过长度。排查技巧如果提交后报“Time Limit Exceeded”第一反应不是算法复杂度问题而是有没有死循环。死循环最常见的来源就是没有取模或者尾部节点的 next 没有置空。5.2 错误二断点定位偏移一位再来一个高频 bug。你确实取模了也确实是先求长度但新链表的长度总是不对。比如输入[1,2,3,4,5]k2正确输出是[4,5,1,2,3]你输出的是[5,1,2,3,4]。这说明你找断点的时候偏移了一位。问题通常出现在while (--move)和for _ in range(move - 1)这两个写法上。如果你把move - 1写成了move等于从原头节点多走了一步新头变成原第 5 个节点。所以排查时建议打印三个值链表长度、计算出的 move、新尾节点的值。新尾节点值一旦不对你立刻能发现是偏移问题而不是逻辑问题。5.3 错误三把头尾接回去以后忘记断尾还有一个非常隐蔽的坑形成了环也找到了新头但忘了把新尾的 next 置空。这时候返回的链表不是链表而是一个循环链表。如果判题系统一跑输出会非常离谱甚至导致程序卡死。原因分析题目给你的原始链表最后一个节点的 next 本来是 null但你把tail.next改成了head如果不把这个环断开链表就没有终点。判断标准很简单如果你在本地跑测试打印链表时出现了重复节点或者内存剧增八成是忘了断尾。我的排查习惯是每次改完指针后在关键位置加一行断言例如# 检查新尾节点 assert new_tail.next is None虽然 LeetCode 上提交时不会执行 assert但本地调试能很快抓到这类问题。5.4 面试中的追问应对这题面试里常见的追问有三个第一“如果 k 是负数怎么办”LeetCode 原题没有这个情况但面试官可能随口问。回答思路是题目定义 k 为非负整数你不需要处理如果一定要扩展可以把负数转成正数右移 -1 位等价于左移 1 位对应k (k % n n) % n。你能答出这个公式面试官基本不会再追问。第二“如果链表有环怎么办”原题假定没有环但面试官可能考你如何检测环。这就跳到 Floyd 判圈算法了你可以回答“先判环再做旋转”一般面试官只是想确认你知道这个边界。第三“如果只给你一个节点的引用怎么把整个链表右移”这个就涉及到对双向链表和尾指针的讨论了。原题给的是头节点所以不需要考虑这个但你有思路就能加分。我自己把这三个追问整理成了一张速查表面试前看一遍很有用。现在也分享给你追问场景核心思路一句话回答模板k 为负取模后加 n 再取模右移 -k 等价左移 k链表有环Floyd 判圈先断环先判环再旋转只给某节点引用无法定位头节点要旋转必须知道头节点能否一趟完成先求长度再取模剪枝需要求长度否则 k 无法归一能否用额外数组可以但不推荐空间 O(1) 才是本题考点5.5 本地调试环境搭建小技巧很多人只在 LeetCode 网页编辑器里写代码遇到 bug 只能靠 print 或者猜。实际上这个题非常适合在本地用 Python 的链表结构做单测。我自己调试时的模板大概是这样的class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_list(arr): dummy ListNode() cur dummy for x in arr: cur.next ListNode(x) cur cur.next return dummy.next def print_list(head): arr [] while head: arr.append(head.val) head head.next print(arr) # 测试 head build_list([1,2,3,4,5]) print_list(head) # [1, 2, 3, 4, 5] head rotateRight(head, 2) print_list(head) # [4, 5, 1, 2, 3] head build_list([1,2,3]) head rotateRight(head, 4) print_list(head) # [2, 3, 1]这样测试的好处是你可以直接构造边界用例比如[1]、[]、k0、k1000000等。LeetCode 的在线判题只告诉你对错不会告诉你具体输出本地调试能帮你更快定位问题。6. 从这题延伸出的链表基本功训练如果你已经能把旋转链表 5 分钟以内写出来我觉得你值得花一点时间做一个“链表基本功三连”训练顺序是反转链表LeetCode 206两两交换链表中的节点LeetCode 24旋转链表LeetCode 61这三个题有着奇妙的递进关系。反转链表让你彻底理解 next 指针是怎么断的两两交换让你练习“多指针协同修改”的节奏旋转链表则把“求长度、取模、找断点、重连”全考了一遍。我当时连续三天每天写一遍这三个题第四天开始所有链表题的代码都干净了很多。原因是这类题太依赖肌肉记忆你光看懂了不行手得跟得上思路。再往深走一步你可以拿旋转链表和循环数组做对比。数组旋转可以用切片一行搞定链表却必须走指针这种对比能帮你建立“数据结构决定算法复杂度”的直觉。说白了面试官问链表题不是真的想知道你会不会旋转链表而是想看你能否把一个对数组很简单的操作迁移到链表的受限模型上。你如果能在回答时自己说出“这个操作数组 O(1) 就能拼接链表必须 O(n) 遍历定位”那这道题你已经不是“刷过”而是“理解”了。我个人在实际操作中的体会是链表题最忌讳死记模板因为代码就那么几行记下来不难但位置稍微一变你就不知道往哪改。最好的学习方式是画图。你可以拿纸画一个 5 节点链表把 tail、newTail、newHead 分别标出来然后拿着图一步步执行代码走两遍之后你会发现“取模找断点”这件事真的不难。如果你现在做题卡住了放下代码先画图画明白了再写效率会高很多。最后再分享一个小技巧LeetCode 提交之前先用三组用例自测——普通场景、k0、k 大于长度。这三组过了这题基本就稳了。我见过太多人只顾着写代码忘了测试边界结果提交败在实际用例上。这种事情经历一次就长记性了希望你不用经历也能记住。
