绮思网站建设qswoo,注册一个空壳公司养着,郑州建网站企业,网页页面设计叫什么从0开始的秋招刷题路#xff0c;记录下所刷每道题的题解#xff0c;帮助自己回顾总结
61. 旋转链表
给你一个链表的头节点 head #xff0c;旋转链表#xff0c;将链表每个节点向右移动 k 个位置。
示例 1#xff1a;
输入#xff1a;head [1,2,3,4,5], k 2 输出记录下所刷每道题的题解帮助自己回顾总结
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 * 10910^9109
思路 解法很直观一句话说就是形成环再移动最后断开
找尾节点形成环形链表 尾节点移动 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)
