061. Rotate List
难度: Medium
刷题内容
原题连接
- https://leetcode-cn.com/problems/rotate-list/
内容描述
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
解题方案
思路 1 **- 时间复杂度: O(N)*- 空间复杂度: O(N)***
将链表存储到数组中，再选择数组，然后再将数组转回链表
代码：
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if (!head || !head.next || k === 0) {
return head;
}
const list = [];
let cur = head;
while (cur) {
list.push(cur)
cur = cur.next;
}
const index = k%list.length;
list.unshift(...list.splice(list.length - index, list.length))
list.forEach((node, index) => {
if (index < list.length) {
node.next = list[index+1]
} else {
node.next = null;
}
})
return list[0]
};
