61. 旋转链表【 力扣(LeetCode) 】

零、原题链接

61. 旋转链表

一、题目描述

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

三、解题思路

3.1 三步走战略

1. 基本思路：
     先反转整个链表，再反转前 k 个结点，再反转后 n-k 个结点。【 k 是求余整个链表长度后的 k】
2. 具体思路：
   • 定义：函数 reverse ，用于反转链表（使用头插法实现）；
   • 预处理：
     • 计算长度，提前返回不需要移动的情况；
     • 增加头指针，方便后续操作；
   • 三步走：
     • 先反转整个链表；
     • 拆分链表，前 k 个为一个链表，后 n-k 个为一个链表；
     • 反转拆分后的两个链表；
     • 合并拆分后的两个链表；

3.2 闭合+断开

• 先计算链表长度，提前返回不需要移动的情况；
• 将链表闭合，形成一个环；
• 确定链表的最后一个结点和头结点，遍历到该结点并断开；

例如：

• 链表：abcde ，k = 2 ；
• 计算链表长度 n = 5 ；
• 链表闭环；
• 确定最后一个链表的位置 = n - (k%n) = 5 - (2%5)=3 ，所以第 3 个 结点就是最后一个结点，那么第 4 个结点就是头结点；【往右移动两次，c 就是最后一个结点，d 就是头结点】

四、参考代码

4.1 三步走战略

时间复杂度：$\mathrm{O}(n)$
空间复杂度：$\mathrm{O}(1)$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head) {
        ListNode* ans = new ListNode();
        ListNode *p = head, *t = nullptr;

        while (p != nullptr) {
            t = p->next;
            p->next = ans->next;
            ans->next = p;
            p = t;
        }

        return ans->next;
    }

    ListNode* rotateRight(ListNode* head, int k) {
        int n = 0;
        for (ListNode* p = head; p != nullptr; p = p->next)
            n++;
        if (n == 0 || k % n == 0)
            return head;

        ListNode* ans = new ListNode(0, head);
        ans->next = reverse(ans->next); // 全部反转

        ListNode* p = ans;
        for (k %= n; k > 0; k--)
            p = p->next;
        head = p->next;
        p->next = nullptr;

        p = ans->next;
        ans->next = reverse(ans->next); // 反转前 k 个
        p->next = reverse(head);        // 反转后 n-k 个并拼接链表

        return ans->next;
    }
};

4.2 闭合+断开

时间复杂度：$\mathrm{O}(n)$
空间复杂度：$\mathrm{O}(1)$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int n = 0;
        ListNode* ans = new ListNode(0, head);
        ListNode* p = ans;
        while (p->next != nullptr) {
            p = p->next;
            n++;
        }
        if (n == 0 || k % n == 0) {
            return head;
        }
        p->next = ans->next;  // 闭合
        for (int i = n - (k % n); i > 0; i--) { // 确定最后一个结点位置
            p = p->next;
        }
        ans->next = p->next; // 确定头结点
        p->next = nullptr;// 断开

        return ans->next;
    }
};

原文地址：https://blog.csdn.net/yyh520025/article/details/142423454

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！