1.题目
61. 旋转链表
难度中等653
给你一个链表的头节点 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]
提示:
迭代法,题目其实就是把那些尾部的放到头部。其实就是对长度 以外的再去求余数,然后将他截断两端,后端的放到前面去。一个整体。然后要注意的是,需要对k=0,没有头节点,以及只有一个节点的做特殊处理。以及k可能被len求余为0,也不需要去旋转了。还有分割节点需要用一个新的变量指针去指。
代码
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if(!head || k === 0 || !head.next) return head;
let len = 0;
let p = head;
while(p) {
p = p.next;
len++;
}
let blockNum = k % len;
if(blockNum === 0) {
return head;
}
// 将倒数几个移动到最前面。
let restNum = len - blockNum;
let prevQ = new ListNode(-1);
prevQ.next = head;
while(restNum) {
prevQ = prevQ.next;
restNum--;
}
let cur = prevQ;
let next = cur.next;
cur.next = null;
let listNode = next;
while(listNode && listNode.next) {
listNode = listNode.next;
}
listNode.next = head;
return next;
};