Medium

题目描述

给你一个链表的头节点 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

解题思路

解题思路

这道题要求将链表向右旋转 k 个位置。我们可以通过以下步骤来解决：

核心思想： 将链表形成环，然后在正确的位置断开。

具体步骤：

  1. 处理边界情况： 如果链表为空、只有一个节点或 k 为 0，直接返回原链表
  2. 计算链表长度： 遍历链表获得总长度 n，同时找到尾节点
  3. 优化 k 值： 由于旋转 n 次等于没有旋转，所以 k = k % n
  4. 形成环形链表： 将尾节点指向头节点
  5. 找到新的尾节点： 从原头节点开始走 n - k 步，找到新的尾节点
  6. 断开环并返回： 新的头节点是新尾节点的下一个节点，将新尾节点的 next 设为 null

时间优化： 通过取模运算避免不必要的旋转，当 k 很大时效果显著。

代码实现

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) {
            return head;
        }
        
        // 计算链表长度并找到尾节点
        ListNode* tail = head;
        int n = 1;
        while (tail->next) {
            tail = tail->next;
            n++;
        }
        
        // 优化 k 值
        k = k % n;
        if (k == 0) {
            return head;
        }
        
        // 形成环形链表
        tail->next = head;
        
        // 找到新的尾节点（从头开始走 n-k 步）
        ListNode* newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail->next;
        }
        
        // 新的头节点
        ListNode* newHead = newTail->next;
        
        // 断开环
        newTail->next = nullptr;
        
        return newHead;
    }
};

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next or k == 0:
            return head
        
        # 计算链表长度并找到尾节点
        tail = head
        n = 1
        while tail.next:
            tail = tail.next
            n += 1
        
        # 优化 k 值
        k = k % n
        if k == 0:
            return head
        
        # 形成环形链表
        tail.next = head
        
        # 找到新的尾节点（从头开始走 n-k 步）
        new_tail = head
        for _ in range(n - k - 1):
            new_tail = new_tail.next
        
        # 新的头节点
        new_head = new_tail.next
        
        # 断开环
        new_tail.next = None
        
        return new_head

public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        // 计算链表长度并找到尾节点
        ListNode tail = head;
        int n = 1;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }
        
        // 优化 k 值
        k = k % n;
        if (k == 0) {
            return head;
        }
        
        // 形成环形链表
        tail.next = head;
        
        // 找到新的尾节点（从头开始走 n-k 步）
        ListNode newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail.next;
        }
        
        // 新的头节点
        ListNode newHead = newTail.next;
        
        // 断开环
        newTail.next = null;
        
        return newHead;
    }
}

var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) return head;
    
    let length = 1;
    let tail = head;
    while (tail.next) {
        tail = tail.next;
        length++;
    }
    
    k = k % length;
    if (k === 0) return head;
    
    let newTail = head;
    for (let i = 0; i < length - k - 1; i++) {
        newTail = newTail.next;
    }
    
    let newHead = newTail.next;
    newTail.next = null;
    tail.next = head;
    
    return newHead;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历链表两次：一次计算长度，一次找到新的尾节点
空间复杂度O(1)只使用常数级别的额外空间

相关题目