LeetCode 补拙笔记 日期：2026.05.27 题目：61. 旋转链表

LeetCode 补拙笔记0. 前言日期2026.05.27题目61. 旋转链表难度中等标签链表、双指针1. 题目理解问题描述给定一个链表的头节点head将链表每个节点向右移动k个位置。示例输入head [1,2,3,4,5],k 2输出[4,5,1,2,3]2. 解题思路核心观察链表长度为n右移k位等价于右移k % n位可以通过找新头、断尾、接原头三步完成原地旋转也可以用三次反转的思路实现整体反转 → 反转前k个 → 反转后n-k个。算法步骤断尾接合法统计链表长度n计算实际旋转步数k k % n找到新尾节点第n-k个节点其下一个节点即为新头断开新尾与新头的连接将原链表尾节点接回原头节点。3. 代码实现packagelc61;classSolution{publicListNoderotateRight(ListNodehead,intk){if(headnull){returnhead;}intn0;ListNodecounthead;while(count.next!null){countcount.next;n;}n;if(n1){returnhead;}kk%n;if(k0){returnhead;}intheadNumn-k;inttailNumn-k-1;ListNodetail;ListNodeoldHeadhead;for(inti0;itailNum;i){headhead.next;}tailhead;headtail.next;tail.nextnull;ListNodelasthead;while(last.next!null){lastlast.next;}last.nextoldHead;returnhead;}publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}}4. 代码优化说明减少分支判断简化逻辑合并变量声明代码更紧凑classSolution{publicListNoderotateRight(ListNodehead,intk){if(headnull)returnnull;// 统计链表长度intsize0;ListNodephead,tailnull;while(p!null){size;tailp;pp.next;}// 计算实际旋转步数k%size;if(k0)returnhead;// 找到新的尾节点第 size - k 个节点ListNodenewTailhead;for(inti1;isize-k;i){newTailnewTail.next;}// 断尾、接原头ListNodenewHeadnewTail.next;newTail.nextnull;tail.nexthead;returnnewHead;}publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}}5. 复杂度分析时间复杂度O(n)O(n)O(n)统计长度、遍历找新尾节点均为线性遍历。空间复杂度O(1)O(1)O(1)仅使用常数级额外指针原地操作。6. 总结核心思路统计长度 断尾接原头是旋转链表最直接高效的实现方式优化后代码减少了冗余变量和分支判断逻辑更清晰可读性更高关键技巧利用链表的尾节点直接接原头节点避免了额外的空间开销实现原地旋转。