Rotate List: 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 * 10^9

Try this Problem on your own or check similar problems:

1. Rotate Array
2. Split Linked List in Parts

Solution:

public ListNode rotateRight(ListNode head, int k) {
    if(head == null) return head;
    ListNode dummy = new ListNode(-1, head), iter = dummy.next, tail = null;

    int listLength = 0;
    while(iter != null){
        ++listLength;
        tail = iter;
        iter = iter.next;
    }

    int numberOfRotations = k % listLength;

    if(numberOfRotations == 0) return head;

    ListNode slow = dummy, fast = dummy;
    while(numberOfRotations-->0){
        fast = fast.next;
    }
    while(fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }

    ListNode newHead = slow.next;
    slow.next = null;
    tail.next = head;

    return newHead;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

We have three pieces to this code:

• First we calculate the length of the list by iterating until we reach null.
• We use list length to determine the number of rotations (if k > listLength, e.g. k=4, listLength=3, after three rotations we will have the same list as if we had not rotations at all, so the only fourth rotation counts k % n). We know how to find the nth element from the end of the list using the approach we implemented in Remove Nth Node From End of List . That node will become the next head of the list after n rotations.
• In the last piece we keep the reference to the newHead which we return as the result of our function. We also break the connection between the rotated part and the rest of the linked list slow.next = null. We connect the tail (the last node) to the non-rotated part of the list that will be shifted right by n places (number of rotations), while the first n nodes of the list will be the rotated part (nodes from nth node to the tail).