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

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

``````  l                r
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
.
.
l               r
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL``````
``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
const dummy = new ListNode(0)
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
}``````

19