LeetCode 题解工作台
旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 示例 1： 输入： head = [1,2,3,4,5], k = 2 输出： [4,5,1,2,3] 示例 2： 输入： head = [0,1,2], k = 4 输出： [2,0,1] 提示： 链表中节点的数目在…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们先判断链表节点数是否小于 ，如果是，直接返回 即可。 否则，我们先统计链表节点数 ，然后将 对 取模，得到 的有效值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]
示例 2：
输入：head = [0,1,2], k = 4 输出：[2,0,1]
提示：
- 链表中节点的数目在范围
[0, 500]内 -100 <= Node.val <= 1000 <= k <= 2 * 109
解题思路
方法一：快慢指针 + 链表拼接
我们先判断链表节点数是否小于 ，如果是，直接返回 即可。
否则，我们先统计链表节点数 ，然后将 对 取模，得到 的有效值。
如果 的有效值为 ，说明链表不需要旋转，直接返回 即可。
否则，我们用快慢指针，让快指针先走 步，然后快慢指针同时走，直到快指针走到链表尾部，此时慢指针的下一个节点就是新的链表头节点。
最后，我们将链表拼接起来即可。
时间复杂度 ，其中 是链表节点数，空间复杂度 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None or head.next is None:
return head
cur, n = head, 0
while cur:
n += 1
cur = cur.next
k %= n
if k == 0:
return head
fast = slow = head
for _ in range(k):
fast = fast.next
while fast.next:
fast, slow = fast.next, slow.next
ans = slow.next
slow.next = None
fast.next = head
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because the list is traversed to find its length and then to relocate pointers. Space complexity is O(1) since no extra structures are needed beyond a few pointers. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect correct pointer updates without creating cycles or losing nodes.
- question_mark
Check handling of k values larger than the list length.
- question_mark
Look for proper empty list and single-node edge case handling.
常见陷阱
外企场景- error
Not using modulo for k, leading to extra unnecessary rotations.
- error
Incorrectly updating the tail node, causing cycles or null references.
- error
Failing to handle lists with length 0 or 1 properly.
进阶变体
外企场景- arrow_right_alt
Rotate list to the left by k positions instead of right.
- arrow_right_alt
Rotate a doubly linked list using similar pointer adjustments.
- arrow_right_alt
Rotate only a subsegment of the list rather than the entire list.