61. Rotate List

BF

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

        // calculate the length of the list
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            length++;
        }

        k = k % length;
        if (k == 0) return head;

        for (int i = 0; i < k; i++) {
            ListNode prev = null;
            ListNode curr = head;

            // find the last and previous node
            while (curr.next != null) {
                prev = curr;
                curr = curr.next;
            }

            // move the last node to the head
            prev.next = null;
            curr.next = head;
            head = curr;
        }

        return head;
    }
}

Remarks:

1. TC: $O(k\times n)$, SC: $O(1)$.

Faster (one pass)

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

        // 1. calculate the length and find the tail
        ListNode oldTail = head;
        int length = 1;
        while (oldTail.next != null) {
            oldTail = oldTail.next;
            length++;
        }

        // 2. make the whole list a ring
        oldTail.next = head;

        // 3. find the new head and tail
        k = k % length;
        int stepsToNewHead = length - k;
        ListNode newTail = head;
        for (int i = 1; i < stepsToNewHead; i++) {
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;

        // 4. break the ring to a list
        newTail.next = null;

        return newHead;
    }
}

Remarks:

1. TC: $O(n)$, SC: $O(1)$.