企业官网建设流程全解析

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个。

算法步骤（断尾接合法）

1. 统计链表长度n，计算实际旋转步数k = k % n；
2. 找到新尾节点（第n-k个节点），其下一个节点即为新头；
3. 断开新尾与新头的连接，将原链表尾节点接回原头节点。

3. 代码实现

packagelc61;classSolution{publicListNoderotateRight(ListNodehead,intk){if(head==null){returnhead;}intn=0;ListNodecount=head;while(count.next!=null){count=count.next;n++;}n++;if(n==1){returnhead;}k=k%n;if(k==0){returnhead;}intheadNum=n-k;inttailNum=n-k-1;ListNodetail;ListNodeoldHead=head;for(inti=0;i<tailNum;i++){head=head.next;}tail=head;head=tail.next;tail.next=null;ListNodelast=head;while(last.next!=null){last=last.next;}last.next=oldHead;returnhead;}publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}}

4. 代码优化说明

减少分支判断，简化逻辑，合并变量声明，代码更紧凑：

classSolution{publicListNoderotateRight(ListNodehead,intk){if(head==null)returnnull;// 统计链表长度intsize=0;ListNodep=head,tail=null;while(p!=null){size++;tail=p;p=p.next;}// 计算实际旋转步数k%=size;if(k==0)returnhead;// 找到新的尾节点（第 size - k 个节点）ListNodenewTail=head;for(inti=1;i<size-k;i++){newTail=newTail.next;}// 断尾、接原头ListNodenewHead=newTail.next;newTail.next=null;tail.next=head;returnnewHead;}publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}}

5. 复杂度分析

• 时间复杂度：O(n)O(n)O(n)
  统计长度、遍历找新尾节点，均为线性遍历。
• 空间复杂度：O(1)O(1)O(1)
  仅使用常数级额外指针，原地操作。

6. 总结

• 核心思路：统计长度 + 断尾接原头，是旋转链表最直接高效的实现方式；
• 优化后代码减少了冗余变量和分支判断，逻辑更清晰，可读性更高；
• 关键技巧：利用链表的尾节点直接接原头节点，避免了额外的空间开销，实现原地旋转。