LeetCode 61. 旋转链表

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 61. 旋转链表

思路分析

计算链表长度：遍历链表计算其长度。

连接成环：将链表尾部连接到头部，形成一个环。

找到新的头节点：根据 k 值计算新的头节点位置，并断开环。

参考代码

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k == 0 {
		return head
	}

	// 1. 计算链表长度
	length := 1
	tail := head
	for tail.Next != nil {
		tail = tail.Next
		length++
	}

	// 2. 处理 k 的值
	k = k % length
	if k == 0 {
		return head
	}

	// 3. 连接成环
	tail.Next = head

	// 4. 找到新的头节点
	newTail := tail
	for i := 0; i < length-k; i++ {
		newTail = newTail.Next
	}
	newHead := newTail.Next

	// 5. 断开环
	newTail.Next = nil

	return newHead
}

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k == 0 {
		return head
	}

	length := 1
	cur := head
	for cur.Next != nil {
		length++
		cur = cur.Next
	}

	k = k % length
	if k == 0 {
		return head
	}

	cur.Next = head

	for i := 0; i < length-k; i++ {
		cur = cur.Next
	}

	newHead := cur.Next
	cur.Next = nil

	return newHead
}

时间复杂度：O(n)，其中 n 是链表的长度。

空间复杂度：O(1)，我们只使用了常数级别的额外空间。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/42871102