61. Rotate List
61. Rotate List
题目
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Constraints:
- The number of nodes in the list is in the range
[0, 500]. -100 <= Node.val <= 1000 <= k <= 2 * 10^9
题目大意
旋转链表 K 次。
解题思路
这道题需要注意的点是，K 可能很大，K = 2000000000 ，如果是循环肯定会超时。应该找出 O(n) 的复杂度的算法才行。由于是循环旋转，最终状态其实是确定的，利用链表的长度取余可以得到链表的最终旋转结果。
代码
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function (head, k) {
if (!head || !head.next || k === 0) return head;
let len = 1;
let prev = head;
let start = new ListNode(0, head);
let end = head;
// 计算链表的长度，并将end指向最末尾的节点
while (end.next) {
len++;
end = end.next;
}
// k 对链表长度取余，避免重复操作
k = k % len;
// 将prev指向链表倒数第k + 1个节点
for (let i = 0; i < len - k - 1; i++) {
prev = prev.next;
}
// 按要求拼接链表
end.next = head;
start.next = prev.next;
prev.next = null;
return start.next;
};