原题地址:旋转链表
给定一个链表,旋转链表,将链表每个节点向右移动 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
准备工作
定义链表节点:
function ListNode(val) {
this.val = val;
this.next = null;
}
数组转链表,方便测试数据的输入:
function arrayT[两两交换链表中的节点](https://blog.lihaiping.cn/archives/swap-nodes-in-pairs)oList(array) {
let node = null;
for (let i = array.length - 1; i >= 0; i --) {
let newNode = new ListNode(array[i]);
newNode.next = node;
node = newNode;
}
return node;
}
链表转字符串,方便测试结果的显示:
function listToString(node) {
return node ? `${node.val}${node.next ? ` -> ${listToString(node.next)}` : '' }` : null;
}
遍历
先遍历一次,确定链表的长度并将尾结点与头结点连接,形成循环链表。然后根据右移的长度,确定新链表应该断裂的位置即可。
具体的实现代码如下:
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
const rotateRight1 = function(head, k) {
// 空链表旋转得到的也是空链表
if (head == null) {
return null;
}
// 额外的头指针方便处理
let preHead = new ListNode(null);
preHead.next = head;
// 记录链表的长度
let count = 0;
while (head.next) {
count ++;
head = head.next;
}
count ++;
// 将链表的尾部与头部连起来
head.next = preHead.next;
// 旋转count次会得到原来的链表,所以需要取模
k = k % count;
// 向右移动k次后,count-k处会断开,形成新的头节点和尾节点
for (let i = 0; i < count - k; i ++) {
head = head.next;
}
preHead.next = head.next;
head.next = null;
// 返回新的头节点
return preHead.next;
};
测试:
let start = new Date();
const test = rotateRight1;
console.log(listToString(test(arrayToList([1,2,3,4,5]),2))); // 4 -> 5 -> 1 -> 2 -> 3
console.log(listToString(test(arrayToList([0,1,2]),4))); // 2 -> 0 -> 1
console.log(new Date().getTime() - start.getTime()); // 7
时间复杂度: 确定链表长度需要一次遍历,确定新的链表头尾节点需要一次遍历,总时间复杂度为$O(2N)=O(N)$
空间复杂度: 原地操作,空间复杂度为$O(1)$
本文由 李海平 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Aug 17,2019