LC 61. 旋转链表

题目描述

这是 LeetCode 上的 61. 旋转链表 ，难度为中等。

给你一个链表的头节点 head，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

1
2
3

输入：head = [1,2,3,4,5], k = 2

输出：[4,5,1,2,3]

示例 2：

1
2
3

输入：head = [0,1,2], k = 4

输出：[2,0,1]

提示：

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

快慢指针

本质还是道模拟题，分步骤处理即可：

避免不必要的旋转：与链表长度成整数倍的「旋转」都是没有意义的（旋转前后链表不变）
使用「快慢指针」找到倒数第 k 个节点（新头结点），然后完成基本的链接与断开与断开操作

Java 代码：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        // 计算有效的 k 值：对于与链表长度成整数倍的「旋转」都是没有意义的（旋转前后链表不变）
        int tot = 0;
        ListNode tmp = head;
        while (tmp != null && ++tot > 0) tmp = tmp.next;
        k %= tot;
        if (k == 0) return head;
        // 使用「快慢指针」找到倒数第 k 个节点（新头结点）：slow 会停在「新头结点」的「前一位」，也就是「新尾结点」
        ListNode slow = head, fast = head;
        while (k-- > 0) fast = fast.next;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 保存新头结点，并将新尾结点的 next 指针置空
        ListNode nHead = slow.next;
        slow.next = null;
        // 将新链表的前半部分（原链表的后半部分）与原链表的头结点链接上
        fast.next = head;
        return nHead;
    }
}

C++ 代码：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || k == 0) return head;
        // 计算有效的 k 值：对于与链表长度成整数倍的「旋转」都是没有意义的（旋转前后链表不变）
        int tot = 0;
        ListNode* tmp = head;
        while (tmp != NULL && ++tot > 0) tmp = tmp->next;
        k %= tot;
        // 使用「快慢指针」找到倒数第 k 个节点（新头结点）：slow 会停在「新头结点」的「前一位」，也就是「新尾结点」
        if (k == 0) return head;
        // 使用快慢指针找到倒数第 k 个节点
        ListNode* slow = head;
        ListNode* fast = head;
        while (k-- > 0) fast = fast->next;
        while (fast->next != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
        // 保存新头结点，并将新尾结点的 next 指针置空
        ListNode* nHead = slow->next;
        slow->next = NULL;
        // 将新链表的前半部分（原链表的后半部分）与原链表的头结点链接上
        fast->next = head;
        return nHead;
    }
};

Python 代码：

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or k == 0: return head
        # 计算有效的 k 值：对于与链表长度成整数倍的「旋转」都是没有意义的（旋转前后链表不变）
        tot, tmp = 0, head
        while tmp:
            tmp = tmp.next
            tot += 1
        k %= tot
        # 使用「快慢指针」找到倒数第 k 个节点（新头结点）：slow 会停在「新头结点」的「前一位」，也就是「新尾结点」
        if k == 0: return head
        # 使用快慢指针找到倒数第 k 个节点
        slow, fast = head, head
        while k > 0:
            fast = fast.next
            k -= 1
        while fast.next:
            slow = slow.next
            fast = fast.next
        # 保存新头结点，并将新尾结点的 next 指针置空
        nHead = slow.next
        slow.next = None
        # 将新链表的前半部分（原链表的后半部分）与原链表的头结点链接上
        fast.next = head
        return nHead

TypeScript 代码：

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (head == null || k == 0) return head;
    // 计算有效的 k 值：对于与链表长度成整数倍的「旋转」都是没有意义的（旋转前后链表不变）
    let tot = 0, tmp = head;
    while (tmp !== null && ++tot > 0) tmp = tmp.next;
    k %= tot;
    // 使用「快慢指针」找到倒数第 k 个节点（新头结点）：slow 会停在「新头结点」的「前一位」，也就是「新尾结点」
    if (k == 0) return head;
    // 使用快慢指针找到倒数第 k 个节点
    let slow = head, fast = head;
    while (k-- > 0) fast = fast.next;
    while (fast.next !== null) {
        slow = slow.next;
        fast = fast.next;
    }
    // 保存新头结点，并将新尾结点的 next 指针置空
    let nHead = slow.next;
    slow.next = null;
    // 将新链表的前半部分（原链表的后半部分）与原链表的头结点链接上
    fast.next = head;
    return nHead;
};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

闭合成环

另外一个做法是，先成环，再断开：

找到原链表的最后一个节点，将其与原链表的头结点相连（成环），并统计链表长度，更新有效 k 值
从原链表的头节点出发，找到需要断开的点，进行断开

Java 代码：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        // 先将链表成环，并记录链表的长度
        // tmp 会记录住原链表最后一位节点
        int tot = 1;
        ListNode tmp = head;
        while (tmp.next != null && ++tot > 0) tmp = tmp.next;
        k %= tot;
        if (k == 0) return head;
        // 正式成环
        tmp.next = head;
        // 从原链表 head 出发，走 tot - k - 1 步，找到「新尾结点」进行断开，并将其下一个节点作为新节点返回
        k = tot - k - 1;
        while (k-- > 0) head = head.next;
        ListNode nHead = head.next;
        head.next = null;
        return nHead;
    }
}

C++ 代码：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || k == 0) return head;
        // 先将链表成环，并记录链表的长度
        // tmp 会记录住原链表最后一位节点
        int tot = 1;
        ListNode* tmp = head;
        while (tmp->next != NULL && ++tot > 0) tmp = tmp->next;
        k %= tot;
        if (k == 0) return head;
        // 正式成环
        tmp->next = head;
        // 从原链表 head 出发，走 tot - k - 1 步，找到「新尾结点」进行断开，并将其下一个节点作为新节点返回
        k = tot - k - 1;
        while (k-- > 0) head = head->next;
        ListNode* nHead = head->next;
        head->next = NULL;
        return nHead;
    }
};

Python 代码：

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or k == 0: return head
        # 先将链表成环，并记录链表的长度
        # tmp 会记录住原链表最后一位节点
        tot, tmp = 1, head
        while tmp.next:
            tmp = tmp.next
            tot += 1
        k %= tot
        if k == 0: return head
        # 正式成环
        tmp.next = head
        # 从原链表 head 出发，走 tot - k - 1 步，找到「新尾结点」进行断开，并将其下一个节点作为新节点返回
        k = tot - k - 1
        while k > 0:
            head = head.next
            k -= 1
        nHead = head.next
        head.next = None
        return nHead

TypeScript 代码：

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (head == null || k == 0) return head;
    // 先将链表成环，并记录链表的长度
    // tmp 会记录住原链表最后一位节点
    let tot = 1, tmp = head;
    while (tmp.next !== null && ++tot > 0) tmp = tmp.next;
    k %= tot;
    if (k == 0) return head;
    // 正式成环
    tmp.next = head;
    k = tot - k - 1;
    while (k-- > 0) head = head.next;
    let nHead = head.next;
    head.next = null;
    return nHead;
};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.61 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

链表

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 173. 二叉搜索树迭代器上一篇

LC 面试题 03.01. 三合一下一篇