Rotate List

Problem

Given the head of a linked list, rotate the list to the right by k places.

 

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

 

Constraints:

• The number of nodes in the list is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

Solution

/**
 * 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) {
    // find length and last node of list
    let len = 1;
    let cur = head;
    while (cur?.next) {
        cur = cur.next;
        len++;
    }
    const tail = cur;

    // rotation amount
    const shift = k % len;
    if (!shift) { // no rotation needed
        return head;
    }

    // rotate list
    cur = head;
    for (let i = 0; i < len - shift - 1; i++) { // get node just before pivot
        cur = cur.next;
    }

    // reconnect list
    tail.next = head;
    head = cur.next;
    cur.next = null;

    return head;
};

First we find the length len of the list head. Since k can be greater then len, rotating by k places is the equivalent of rotating by shift = k % len places. To do so, we split up the list into two, one in the index range [0, len - shift - 2] and the other in the index range [len - shift - 1, len - 1] (ie. the first len - k elements in the first list, and the last k elements in the second list). Next, by connecting the first list to the end of the second list we get our desired rotation.