力扣第 61 题旋转链表

题目描述

给定一个链表，旋转链表，将链表中的每个节点向右移动 $k$ 个位置，其中 $k$ 是非负数。

示例 1:

输入: head = [1,2,3,4,5], k = 2
输出: [4,5,1,2,3]
解释:
向右旋转 1 步: [5,1,2,3,4]
向右旋转 2 步: [4,5,1,2,3]

示例 2:

输入: head = [0,1,2], k = 4
输出: [2,0,1]
解释:
向右旋转 1 步: [2,0,1]
向右旋转 2 步: [1,2,0]
向右旋转 3 步: [0,1,2]
向右旋转 4 步: [2,0,1]

约束:

• 链表中的节点数在范围 $[0,500]$ 内。
• $-100\le Node.val\le 100$。
• $0\le k\le 2\ast 10^9$。

解题思路

1. 特殊情况处理:

   • 如果链表为空或只有一个节点，或者 $k=0$，直接返回原链表。

2. 计算链表长度:

   • 遍历链表，计算链表长度$n$。

3. 优化旋转步数:

   • 由于旋转 $k$ 次相当于旋转 $k\%n$ 次，减少多余计算。

4. 找到旋转点:

   • 新的头节点的位置是 $n-(k\%n)$。需要找到链表中对应的位置，将链表断开并重新连接。

5. 形成环再断开:

   • 可以将链表连成环，然后在适当位置断开。

C 代码实现

以下是基于上述思路的 C 语言实现：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 旋转链表函数
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (!head || !head->next || k == 0) {
        return head; // 特殊情况直接返回
    }

    // 计算链表长度
    int n = 1;
    struct ListNode *tail = head;
    while (tail->next) {
        tail = tail->next;
        n++;
    }

    // 优化 k，计算实际旋转步数
    k = k % n;
    if (k == 0) {
        return head; // 如果 k 为 0，不需要旋转
    }

    // 将链表连成环
    tail->next = head;

    // 找到新头节点和新尾节点
    int stepsToNewHead = n - k;
    struct ListNode *newTail = head;
    for (int i = 1; i < stepsToNewHead; i++) {
        newTail = newTail->next;
    }
    struct ListNode *newHead = newTail->next;

    // 断开环
    newTail->next = NULL;

    return newHead;
}

// 辅助函数：创建新节点
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 辅助函数：打印链表
void printList(struct ListNode* head) {
    while (head) {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

// 主函数测试
int main() {
    // 创建链表 [1, 2, 3, 4, 5]
    struct ListNode *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    printf("原始链表: ");
    printList(head);

    int k = 2;
    struct ListNode *rotated = rotateRight(head, k);

    printf("旋转链表后: ");
    printList(rotated);

    return 0;
}

代码解析

1. 特殊情况处理:

   • 如果链表为空、只有一个节点，或者 $k=0$，直接返回原链表，避免无意义操作。

2. 链表长度计算:

   • 遍历链表，记录长度 $n$ 并找到尾节点 tail。

3. 优化旋转步数:

   • 使用 $k\%n$ 计算有效旋转次数。如果结果为 0，说明无需旋转。

4. 形成环并找到新头:

   • 将链表尾节点连接到头节点，形成环。
   • 根据 stepsToNewHead 找到新尾节点 newTail，然后确定新头节点 newHead。

5. 断开环:

   • 将 newTail->next 设置为 NULL，完成旋转。

复杂度分析

• 时间复杂度: $O(n)$
  • 遍历链表计算长度需要 $O(n)$。
  • 找到新头节点需要 $O(n)$。
• 空间复杂度: $O(1)$
  • 只使用了常量级的额外空间。

测试结果

输入：

head = [1,2,3,4,5], k = 2

输出：

旋转链表后: 4 -> 5 -> 1 -> 2 -> 3 -> NULL