61. 旋转链表

题意

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

难度

中等

示例

示例 1：

1668917473878-e2e7cbec-3726-4576-a6bd-69234d5894bf.jpeg

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

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

示例 2：

1668917490527-73d973d9-4b1b-4aa4-9d96-b1bb1381115c.jpeg

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

输出：[2,0,1]

分析

我们先把如何 ”旋转“ 链表的这个问题放在一边，来思考向右移动 k 个位置后链表的状

态。

观察例 2 的过程，我们可以发现，当向右移动 sizeOfList 次之后，链表会恢复原有的样

子。

换言之，我们并不需要移动完整的 k 次，而是仅仅需要移动 k % sizeOfList 次即可。

那么我们接下来来看看如何 ”旋转“ 链表。

旋转链表需要把后 k 个节点移动到最前面，并且把最后一个节点的下一个节点设置成原本

的头节点。

能不能把顺序倒过来呢？

我们先把最后一个节点的下一个节点设置为原本的头节点，让整个链表成为一个环形的循

环链表，然后再在距离原本头节点 sizeOfList - k % sizeOfList 处断开，这样子就能把倒

数第 k 个节点变成新的头节点，这时候，返回它就可以了。

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

*}

*/

class Solution {

public ListNode rotateRight(ListNode head, int k) {

if(k == 0 || head == null || head.next == null)

return head;

int sizeOfList = 1;

ListNode tail = head;

while(tail.next != null){

tail = tail.next;//获取整个链表最末端的节点

sizeOfList++;//计算链表长度

}

int breakPos = sizeOfList - k % sizeOfList;//断开的位置

if(breakPos == sizeOfList)

return head;

tail.next = head;//将链表变为循环链表

while(breakPos-- > 0){

tail = tail.next;//移动到应该断开的位置

}

ListNode newHead = tail.next;

tail.next = null;//断开

return newHead;

}

}

1668917509675-608252c0-2ba7-4b29-b485-cc9f37751a29.png

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

n 为整个链表的长度（即 sizeOfList），因为我们找出了向右移动 sizeOfList 次后，链表

会恢复到原本的样子的这一特性，从而不用去频繁执行移动操作，整个算法流程最差情况

（当 breakPos == n - 1）时，我们才需要遍历整个链表 2n - 1 次，其余情况均不会超过

2n - 1。所以时间复杂度为$ O(n) $。

总结

本题我们找出了链表移动的规律，从而避免了大量的移动造成的时间浪费，使得我们能够

快速解决本题。

力扣链接：https://leetcode.cn/problems/rotate-list/