'# Golang | Leetcode Golang题解之第61题旋转链表
一、背景与问题
LeetCode 第 61 题「旋转链表」要求我们对单向链表进行旋转操作。题目描述如下：
给你一个链表，旋转一定的次数后，返回旋转后的链表。
例如，输入链表 1->2->3->4->5，旋转 2 次后，结果应为 4->5->1->2->3。
该问题的核心在于理解链表旋转的逻辑，以及如何高效地实现这一逻辑。我们需要考虑以下关键点：
- 如何高效计算旋转后的头节点
- 如何处理边界情况（如空链表、n=0、n大于链表长度等）
- 如何避免重复遍历链表，提高性能
二、基本原理
1. 旋转链表的逻辑
旋转链表的本质是将链表的末尾部分移动到头部。例如，旋转一次相当于将链表的最后一位节点移动到头部，旋转两次则将倒数第二位节点移动到头部。
假设链表长度为 length，旋转次数为 n。我们可以将旋转次数简化为 n % length（当 n >= length 时），这样可以避免不必要的重复旋转。
2. 找到分割点
假设链表长度为 length，旋转次数为 k，则分割点位置为 length - k。例如，对于链表 1->2->3->4->5，当 k=2 时，分割点为位置 5-2=3，即节点 3。将链表拆分为两部分：1->2->3 和 4->5，然后将第二部分连接到第一部分的末尾。
3. 处理特殊情况
- 空链表：直接返回
nil - n=0：无需旋转，直接返回原链表
- n > length：通过取模操作简化旋转次数
三、环境准备
确保你的开发环境支持 Go 1.18+，并安装必要的工具：
# 安装 Go
https://golang.org/dl/
# 验证安装
go version
四、核心实现
1. 常规实现（两次遍历）
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
// 第一次遍历：计算链表长度
length := 0
current := head
for current != nil {
current = current.Next
length++
}
// 计算有效旋转次数
k = k % length
if k == 0 {
return head
}
// 第二次遍历：找到分割点
current = head
for i := 1; i < length - k; i++ {
current = current.Next
}
// 分割链表
newHead := current.Next
current.Next = nil
// 合并两部分
tail := newHead
for tail.Next != nil {
tail = tail.Next
}
tail.Next = head
return newHead
}
关键代码解释：
- 第一次遍历：计算链表长度，确保代码处理空链表的情况。
- k % length：处理旋转次数超过链表长度的情况，避免重复遍历。
- 第二次遍历：找到分割点，将链表拆分为两部分。
- 合并两部分：找到第二部分的尾节点，将其连接到原链表的头部。
2. 快慢指针法（一次遍历）
func rotateRightFast(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
// 计算链表长度
length := 0
current := head
for current != nil {
current = current.Next
length++
}
// 计算有效旋转次数
k = k % length
if k == 0 {
return head
}
// 快慢指针法
slow, fast := head, head
for i := 0; i < k; i++ {
fast = fast.Next
}
// 找到分割点
for fast.Next != nil {
slow = slow.Next
fast = fast.Next
}
// 分割链表
newHead := slow.Next
slow.Next = nil
// 合并两部分
tail := newHead
for tail.Next != nil {
tail = tail.Next
}
tail.Next = head
return newHead
}
关键代码解释：
- 快慢指针：通过快指针移动
k 次，找到分割点。快指针始终比慢指针快 k 步，最终慢指针指向分割点。 - 一次遍历：减少遍历次数，提高性能。
3. 优化版实现（处理空链表和边界情况）
func rotateRightOptimized(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
// 计算链表长度
length := 0
current := head
for current != nil {
current = current.Next
length++
}
// 计算有效旋转次数
k = k % length
if k == 0 {
return head
}
// 快慢指针法
slow, fast := head, head
for i := 0; i < k; i++ {
fast = fast.Next
}
// 找到分割点
for fast.Next != nil {
slow = slow.Next
fast = fast.Next
}
// 分割链表
newHead := slow.Next
slow.Next = nil
// 合并两部分
tail := newHead
for tail.Next != nil {
tail = tail.Next
}
tail.Next = head
return newHead
}
关键代码解释：
- 优化处理：对空链表和
k=0 的情况直接返回原链表，避免冗余计算。 - 性能优化：使用快慢指针法，仅遍历一次链表。
五、完整案例
案例描述
输入链表：1->2->3->4->5，旋转 2 次，输出应为 4->5->1->2->3。
实现代码
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
// 计算链表长度
length := 0
current := head
for current != nil {
current = current.Next
length++
}
// 计算有效旋转次数
k = k % length
if k == 0 {
return head
}
// 快慢指针法
slow, fast := head, head
for i := 0; i < k; i++ {
fast = fast.Next
}
// 找到分割点
for fast.Next != nil {
slow = slow.Next
fast = fast.Next
}
// 分割链表
newHead := slow.Next
slow.Next = nil
// 合并两部分
tail := newHead
for tail.Next != nil {
tail = tail.Next
}
tail.Next = head
return newHead
}
func main() {
// 构造链表 1->2->3->4->5
head := &ListNode{Val: 1}
head.Next = &ListNode{Val: 2}
head.Next.Next = &ListNode{Val: 3}
head.Next.Next.Next = &ListNode{Val: 4}
head.Next.Next.Next.Next = &ListNode{Val: 5}
// 旋转链表
rotatedHead := rotateRight(head, 2)
// 打印结果
for rotatedHead != nil {
fmt.Printf("%d -> ", rotatedHead.Val)
rotatedHead = rotatedHead.Next
}
fmt.Println("nil")
}
运行结果：
4 -> 5 -> 1 -> 2 -> 3 -> nil
代码解释
- 构造了一个长度为5的链表，旋转2次后，输出结果符合预期。
- 使用快慢指针法，在一次遍历中完成分割和合并操作。
六、源码解析
1. 快慢指针法原理
- 快指针：从头节点开始，移动
k 次，最终指向分割点的前一个节点。 - 慢指针：始终比快指针慢
k 步，最终指向分割点。 - 分割点：快指针到达链表末尾时，慢指针指向分割点。
2. 分割链表逻辑
newHead := slow.Next：获取第二部分的头节点。slow.Next = nil：将原链表分割为两部分。tail.Next = head：将第二部分的尾节点连接到原链表的头部。
3. 边界条件处理
- 空链表：直接返回
nil。 - n=0：无需旋转，直接返回原链表。
- n > length：通过
k = k % length 简化旋转次数。
七、进阶使用
1. 多次旋转优化
在实际项目中，如果需要对链表进行多次旋转操作，可以考虑预处理旋转次数，避免重复计算。
func rotateMultipleTimes(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
// 预处理旋转次数
length := 0
current := head
for current != nil {
current = current.Next
length++
}
k = k % length
if k == 0 {
return head
}
// 实现同上...
}
2. 链表旋转与循环链表的结合
在某些场景下，链表可能需要循环处理。例如，在缓存系统中，使用链表实现LRU缓存时，可能需要对链表进行旋转操作。
3. 性能优化
对于大规模链表数据，可以考虑使用数组存储节点，减少指针操作的开销。
八、性能与工程实践
1. 时间复杂度
- 常规实现：O(n) 时间复杂度，两次遍历。
- 快慢指针法：O(n) 时间复杂度，一次遍历。
- 优化版：O(n) 时间复杂度，一次遍历。
2. 空间复杂度
- 所有实现的空间复杂度均为 O(1)，仅使用少量指针。
3. 异常处理
- 空链表：直接返回
nil。 - n=0：无需旋转，直接返回原链表。
- n > length：通过取模操作简化旋转次数。
4. 安全风险
- 空指针访问：在断开链表时，需要确保指针非
nil。 - 循环引用：在合并链表时，要避免形成循环链表。
5. 代码可维护性
- 使用快慢指针法使代码更简洁，易于维护。
- 对边界情况的处理提高代码健壮性。
九、常见问题与踩坑
1. 忘记处理 k=0 的情况
错误代码：
func rotateRightWrong(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 其他逻辑
}
问题：未处理 k=0 的情况，导致不必要的旋转。
解决方法：在代码开头增加 if k == 0 的判断。
2. 未处理 k > length 的情况
错误代码：
func rotateRightWrong2(head *ListNode, k int) *ListNode {
// 其他逻辑
k = k % length
// 其他逻辑
}
问题：未处理 k > length 的情况，导致多次遍历。
解决方法：在计算 k 时，使用 k = k % length。
3. 快慢指针未正确移动
错误代码：
for i := 0; i < k; i++ {
fast = fast.Next
}
问题：未考虑快指针初始位置，导致分割点计算错误。
解决方法：确保快指针从头节点开始移动 k 次。
4. 合并链表时未找到尾节点
错误代码：
tail := newHead
tail.Next = head
问题：未找到尾节点，导致链表循环。
解决方法：遍历找到尾节点，再连接到原链表头部。
十、最佳实践
1. 使用快慢指针法
- 快慢指针法仅遍历一次链表，提高性能。
- 适用于大多数场景，尤其是需要频繁旋转链表的场景。
2. 处理边界情况
- 在代码开头处理
head == nil、k == 0 等边界条件。 - 避免因边界条件导致的错误或死循环。
3. 预处理旋转次数
- 在多次旋转操作中，预处理
k 的值，避免重复计算。 - 提高代码效率，减少不必要的遍历。
4. 确保链表无循环
- 在合并链表时，确保尾节点的
Next 指向原链表头部，而非自身。 - 避免形成循环链表，导致无法遍历。
十一、总结
LeetCode 第 61 题「旋转链表」是链表操作中的经典问题，其核心在于理解链表旋转的逻辑和高效实现。通过快慢指针法，我们可以在一次遍历中完成链表的分割和合并，从而提高代码性能。
在实际开发中，旋转链表的场景可能包括缓存系统、数据队列处理等。在这些场景中，合理使用链表旋转可以提高数据处理效率。
需要注意的是，旋转链表的实现必须考虑边界条件，如空链表、旋转次数为零等情况。此外，避免形成循环链表是确保代码健壮性的关键。
总之，通过深入理解旋转链表的原理和实现细节，我们可以编写出高效、可靠的链表操作代码，为实际项目提供支持。