Leetcode力扣秋招刷题路-0061

从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结

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 * $10^9$

思路
解法很直观，一句话说就是形成环，再移动，最后断开

找尾节点，形成环形链表
尾节点移动 length - k 步，（右移k步 == 左移 length - k 步）
找到头节点，断开头尾连接

一些细节见代码👇

class Solution {public ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null){return head;}// 1. 找尾节点，形成环形链表ListNode tail = head;int length = 1;while(tail.next != null){length++;tail = tail.next;}tail.next = head;// 2. 尾节点移动 length - k 步k = k % length;for(int i = 0; i < length - k; i++){tail = tail.next;}// 3. 找到头节点，断开头尾连接head = tail.next;tail.next = null;return head;}
}

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