☕ DSA Java Articles

Topics › Linked List › Hard Problems of LL

Rotate a LL

Hard TUF ID 2843 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list and a non-negative integer k. Rotate the list to the right by k places: in each single rotation the last node is moved to the front. Return the head of the rotated list. k may be much larger than the length of the list.

Constraints: 0 ≤ n ≤ 500, 0 ≤ k ≤ 2 × 10^9, values fit in an int.

Example 1

head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
answer = 4 -> 5 -> 1 -> 2 -> 3     // the last two nodes move to the front, in their original order

Example 2

head = 0 -> 1 -> 2, k = 4
answer = 2 -> 0 -> 1               // 4 rotations of a 3-node list equal 1 rotation

Example 3

head = 1 -> 2 -> 3, k = 3
answer = 1 -> 2 -> 3               // a full turn changes nothing

Approach 1: Brute force, rotate one step at a time

Intuition. Do exactly what the statement says, k times: find the last node, detach it from the second-to-last node, and put it in front of the head. Each step is a full walk of the list because a singly linked list gives no quick way to reach its tail.

Algorithm.

  1. If the list has fewer than two nodes, return it.
  2. Repeat k times:
    • Walk secondLast until secondLast.next.next == null.
    • Let last = secondLast.next; set secondLast.next = null, last.next = head, head = last.
  3. Return head.
static ListNode bruteForce(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    for (int i = 0; i < k; i++) {
        ListNode secondLast = head;
        while (secondLast.next.next != null) secondLast = secondLast.next;
        ListNode last = secondLast.next;
        secondLast.next = null;                       // detach the tail node
        last.next = head;                             // and put it in front
        head = last;
    }
    return head;
}

Complexity. Time O(n × k): k rotations, each a linear walk. Space O(1).

With k up to 2 × 10^9 this is hopeless even for a tiny list. The waste is obvious once you notice two facts. First, rotating by n returns the list to its original state, so only k mod n rotations matter. Second, those k mod n rotations together move one contiguous suffix of the list to the front; we should move the whole suffix at once instead of one node at a time.

Approach 2: Better, shift the values through an array

Intuition. Reduce k to shift = k mod n. Rotating right by shift means the node at position i in the result holds the value that was at position (i - shift) mod n in the original. Copy the values into an array, then walk the list once more writing the shifted values back. The nodes stay where they are; only their values move.

Algorithm.

  1. If the list is empty, return null.
  2. Copy the values into vals; let n be the size and shift = k % n.
  3. For each position i from 0 to n - 1, write vals[(i - shift + n) % n] into the i-th node.
  4. Return head.
static ListNode better(ListNode head, int k) {
    if (head == null) return null;
    List<Integer> vals = new ArrayList<>();
    for (ListNode t = head; t != null; t = t.next) vals.add(t.val);
    int n = vals.size(), shift = k % n;
    ListNode t = head;
    for (int i = 0; i < n; i++) {
        t.val = vals.get((i - shift + n) % n);        // position i of the result holds position i - shift of the original
        t = t.next;
    }
    return head;
}

Complexity. Time O(n): two passes over the list. Space O(n) for the copied values.

The + n before % n matters: in Java, (i - shift) % n is negative when i < shift, and a negative index would throw. Adding n first keeps the operand in [0, 2n), so the remainder is a valid index.

This removes the dependence on k but still uses linear extra memory, and it moves values instead of nodes. The expected solution does the rotation with pointers alone.

Approach 3: Optimal, close the ring and cut it

Intuition. A right rotation by shift takes the last shift nodes and puts them in front. Equivalently: the node at position n - shift (1-based) becomes the new tail, the node after it becomes the new head, and the old tail must connect to the old head. The cleanest way to perform all three changes is to first join the tail to the head, turning the list into a ring, then walk n - shift - 1 steps from the old head to reach the new tail, record newHead = newTail.next, and cut the ring there. One pass to count and find the tail, one shorter walk to the cut point.

Algorithm.

  1. If the list has fewer than two nodes, return it.
  2. Walk to the tail, counting n nodes.
  3. Compute shift = k % n. If shift == 0, return head unchanged.
  4. Set tail.next = head to close the ring.
  5. Starting at head, move n - shift - 1 times to reach newTail (the (n - shift)-th node).
  6. Set newHead = newTail.next, then newTail.next = null.
  7. Return newHead.
static ListNode optimal(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    int n = 1;
    ListNode tail = head;
    while (tail.next != null) { tail = tail.next; n++; }
    int shift = k % n;
    if (shift == 0) return head;                      // whole turns change nothing
    tail.next = head;                                 // close the ring
    ListNode newTail = head;
    for (int i = 1; i < n - shift; i++) newTail = newTail.next;    // node number n - shift (1-based) becomes the new tail
    ListNode newHead = newTail.next;
    newTail.next = null;                              // open the ring again
    return newHead;
}

Dry run on 1 -> 2 -> 3 -> 4 -> 5, k = 2:

step state
count n = 5, tail = 5
shift 2 % 5 = 2
close ring 5.next = 1
walk n - shift - 1 = 2 steps from 1 newTail = 3
newHead 3.next = 4
cut 3.next = null

Result: 4 -> 5 -> 1 -> 2 -> 3.

Complexity. Time O(n): the counting walk is n steps and the second walk is fewer than n. Space O(1).

Why return early when shift == 0? With shift = 0 the new tail would be node n, which is the old tail, and newHead would be tail.next = head: the code would still produce the correct result after closing and reopening the ring. The early return just avoids pointless pointer writes and makes the “full turn” case explicit.

Why does the ring trick make the cut easy? In a straight list, moving the suffix requires three separate pointer changes on nodes that are far apart (the old tail, the new tail, and the head). Closing the ring performs the “old tail to old head” link up front, after which the rotation is just a single cut anywhere on the ring. Where to cut is determined purely by counting.

Edge cases and pitfalls