题目

标题和出处

标题：旋转链表

出处：61. 旋转链表

难度

4 级

题目描述

要求

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

示例

示例 1：

输入：
输出：

示例 2：

输入：
输出：

数据范围

• 链表中结点的数目在范围 内
• 
• 

解法

思路和算法

如果链表为空，则直接返回空链表即可。只有当链表不为空时，才需要考虑旋转后的列表。

假设链表的长度为 ，即链表包含 个结点，则将链表向右旋转 个位置之后回到原始链表。因此，将链表向右旋转 个位置等价于将链表向右旋转 个位置。令 ，使得 ，再考虑链表向右旋转 个位置之后的结果。以下只考虑 的情况。

当 时，旋转后的链表为原始链表，因此直接返回 。

当 时，需要考虑旋转后的链表的头结点和尾结点。由于新的头尾结点一定和原始的头尾结点不同，因此首先将原始链表的尾结点和头结点相接，使得链表变成环，然后定位到新的头尾结点并将连接断开，返回新的头结点作为旋转后的链表。

将原始链表向右旋转 个位置之后，原始链表的倒数第 个结点变成新的头结点，等价于原始链表的正数第 个结点，新的尾结点是原始链表的正数第 个结点。因此，从原始链表的头结点开始向后移动 步即可得到新的尾结点，新的尾结点的后面一个结点即为新的头结点。

用 表示原始链表的尾结点，用 和 表示旋转后的新的头结点和尾结点。遍历链表到最后一个结点即可定位 ，将链表变成环只需要令 即可。从 出发，向后移动 次即可定位到 ， 即为 ，令 即可断开新的头尾结点之间的连接。最后返回 即可。

代码

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }
        k %= n;
        if (k == 0) {
            return head;
        }
        tail.next = head;
        int newTailIndex = n - k;
        ListNode newTail = head;
        for (int i = 1; i < newTailIndex; i++) {
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=uypTC)，其中 是链表的长度。需要遍历链表一次，计算链表长度和定位到尾结点，然后再次遍历链表定位到新的头尾结点，将链表连接成环和在新的头尾结点处断开连接的操作都是 #card=math&code=O%281%29&id=pOgUC) 的时间。
• 空间复杂度：#card=math&code=O%281%29&id=T7HIT)。