61.Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Analyze

分析: 该题可以转化为从尾部向前数到第 k 个元素, 将该元素作为头节点, 同时将初始尾节点的下一个节点指向初始头节点。

  1. 第一步: 遍历一遍链表得到初始尾结点 last;
  2. 第二步: l 与 r 距离保持为 modK + 1;
  3. 第三步: l 与 r 同时向右移动, 直到 r 为 null, 则 l 为要分割的元素;

此外如果链表长度为 0 或者链表长度与 k 相等时, 则链表实际上没有旋转交换位置。

l r
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
.
.
l r
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
/**
* 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) {
const dummy = new ListNode(0)
dummy.next = head
let count = 0
let last = dummy
while (last.next) {
last = last.next
count++
}
if (count === 0 || count === k) return dummy.next
const modK = k % count
let diff = modK + 1
let l = dummy
let r = dummy
while (diff--) {
r = r.next
}
while (r) {
r = r.next
l = l.next
}
last.next = dummy.next
dummy.next = l.next
l.next = null
return dummy.next
}

Sister Title

19