0061. 旋转链表【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 闭合成环再断开

1. 📝 题目描述

• 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]

---

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9

2. 🎯 s.1 - 闭合成环再断开

c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (!head || !head->next || k == 0)
        return head;

    // 计算链表长度，并找到尾节点
    int len = 1;
    struct ListNode* tail = head;
    while (tail->next) {
        tail = tail->next;
        len++;
    }

    k %= len;
    if (k == 0)
        return head;

    tail->next = head; // 尾节点接头，形成环

    // 找到新的尾节点（从 head 走 len - k - 1 步）
    struct ListNode* newTail = head;
    for (int i = 0; i < len - k - 1; i++)
        newTail = newTail->next;

    struct ListNode* newHead = newTail->next;
    newTail->next = NULL; // 断开环
    return newHead;
}

js

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function (head, k) {
  if (!head || !head.next || k === 0) return head

  // 计算链表长度，并找到尾节点
  let len = 1
  let tail = head
  while (tail.next) {
    tail = tail.next
    len++
  }

  k %= len
  if (k === 0) return head

  tail.next = head // 尾节点接头，形成环

  // 找到新的尾节点（从 head 走 len - k - 1 步）
  let newTail = head
  for (let i = 0; i < len - k - 1; i++) newTail = newTail.next

  const newHead = newTail.next
  newTail.next = null // 断开环
  return newHead
}

py

# 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 not head or not head.next or k == 0:
            return head

        # 计算链表长度，并找到尾节点
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1

        k %= length
        if k == 0:
            return head

        tail.next = head  # 尾节点接头，形成环

        # 找到新的尾节点（从 head 走 length - k - 1 步）
        new_tail = head
        for _ in range(length - k - 1):
            new_tail = new_tail.next

        new_head = new_tail.next
        new_tail.next = None  # 断开环
        return new_head

• 时间复杂度：$O(n)$，其中 n 是链表长度，最多遍历两次链表
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 遍历链表求长度 len，同时找到尾节点 tail
• 将 k 对 len 取模，若 k == 0 则无需旋转
• 将 tail.next 指向 head 形成环，从 head 向前走 len - k - 1 步找到新尾节点
• 新尾节点的下一个节点即为新头节点，断开环返回新头