0061.md

61. Rotate List

Level:

Topic:

Question

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

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

Intuition

1. Calculate the number of nodes in the list
2. k % = n is the parition index of two lists
3. if k == 0, no need to rotate
4. get the first list
5. get the second list
6. connect two list
7. return the new head

Code

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

public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;

        // count the nodes in the list
        int n = 1;
        ListNode oldTail = head;
        while (oldTail.next != null) {
            n++;
            oldTail = oldTail.next;
        }

        // check if the rotate part is equal to the whole list
        k = k % n;
        if (k == 0) return head;

        // split the list by n-k and k
        ListNode kth = head;
        while (k-- >= 0)
            kth = kth.next;

        ListNode prev = head;
        while (kth != null) {
            prev = prev.next;
            kth = kth.next;
        }

        ListNode newHead = prev.next;
        prev.next = null;
        oldTail.next = head;

        return newHead;
    }