Topics › Linked List › Hard Problems of LL

Rotate a LL

Hard TUF ID 615 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given the head of a singly linked list and a non-negative integer k, rotate the list to the right by k places and return the new head. One rotation to the right takes the last node off the end and puts it in front of the head.

Constraints: 0 ≤ n ≤ 500 nodes, 0 ≤ k ≤ 2 × 10^9. The large k is the real point of the problem: a solution whose running time grows with k will not finish.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

Example 1

head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
after 1 rotation:  5 -> 1 -> 2 -> 3 -> 4
after 2 rotations: 4 -> 5 -> 1 -> 2 -> 3      // answer

Example 2

head = 0 -> 1 -> 2, k = 4
answer = 2 -> 0 -> 1      // 3 rotations bring the list back, so 4 rotations equal 1

Approach 1: Brute force, simulate one rotation at a time

Intuition. Do exactly what the definition says, k times. One rotation needs the last node and the node before it: walk to the second-to-last node, detach the last node, point it at the current head, and make it the new head.

Algorithm.

1. If the list has fewer than two nodes, return it unchanged (rotation cannot change it).
2. Repeat k times:
   • Walk beforeLast until beforeLast.next.next == null.
   • last = beforeLast.next; set beforeLast.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 step = 0; step < k; step++) {
        ListNode beforeLast = head;
        while (beforeLast.next.next != null) beforeLast = beforeLast.next;
        ListNode last = beforeLast.next;
        beforeLast.next = null;                     // last node leaves the end ...
        last.next = head;                           // ... and becomes the new head
        head = last;
    }
    return head;
}

Complexity. Time O(n × k): each rotation walks the list. Space O(1).

With k = 2 × 10^9 this does billions of walks. Even if we first reduce k modulo n (see below), the cost is still O(n^2) in the worst case, and the repeated walking is pure waste: every rotation rediscovers the same end of the list.

Approach 2: Optimal, one cut and one splice

Intuition. Two observations remove all the repetition.

1. Rotating n times gives the original list back. Each node moves forward one position per rotation, so after n rotations everything is back where it started. Only k mod n rotations matter. In Example 2, 4 mod 3 = 1.
2. Rotating right by k moves the last k nodes, in order, to the front. Look at Example 1: the last two nodes 4 5 end up at the front, still in the order 4 5, followed by 1 2 3. So the whole operation is: cut the list just before its last k nodes, and attach the original front part after the original tail.

The node just before the cut is the (n - k)-th node (1-based); it becomes the new tail. The node after it becomes the new head. The old tail, which we already found while counting, gets linked to the old head.

Algorithm.

1. If the list has fewer than two nodes, return it.
2. Walk to the tail while counting the length n.
3. k = k mod n. If k == 0, return head unchanged.
4. Walk to the (n - k)-th node, newTail. Let newHead = newTail.next.
5. Set newTail.next = null and tail.next = head.
6. 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++;
    }
    k %= n;                                         // rotating by n gives the same list back
    if (k == 0) return head;
    ListNode newTail = head;
    for (int i = 1; i < n - k; i++) newTail = newTail.next;   // the (n - k)-th node
    ListNode newHead = newTail.next;
    newTail.next = null;
    tail.next = head;                               // old tail now leads into the old head
    return newHead;
}

Dry run on Example 1 (1 2 3 4 5, k = 2):

On Example 2, n = 3, k = 4 mod 3 = 1, newTail is the 2nd node (1), newHead is 2, and splicing 2.next = 0 gives 2 -> 0 -> 1.

Complexity. Time O(n): one pass to count, at most one more partial pass to find newTail. Space O(1). The running time no longer depends on k at all.

A popular variant of the same idea first links the tail to the head to form a ring, walks n - k steps from the tail, and breaks the ring there. It does the same work; the version above just avoids creating a temporary cycle.

Edge cases and pitfalls

• Empty list or single node. Rotation cannot change them. The early return also avoids dividing by zero in k % n when n = 0.
• k = 0 or k a multiple of n. The early return after k %= n is essential, not an optimisation. Without it, newTail would be the old tail and newHead would be null; then tail.next = head would turn the list into a cycle and the method would return null.
• Huge k. k can be close to 2^31 - 1. The modulo makes it harmless. The Java tests call the optimal method with Integer.MAX_VALUE and skip the brute force for that case, since simulating it would take far too long; a separate test with k = 1 000 000 on a three-node list does exercise the brute force.
• Left versus right. Rotating left by k equals rotating right by n - (k mod n). Read the statement carefully; this problem rotates to the right.
• Off-by-one in the walk. newTail starts at the head (node 1) and moves n - k - 1 times, landing on node n - k. The loop for (int i = 1; i < n - k; i++) expresses exactly that.

Related problems

• Rotate a LL is the same problem in the A2Z sheet.
• Left Rotate Array by K Places is the array version, where the same k mod n reduction applies.
• Reverse LL in group of given size K is another problem built from cutting a list and reconnecting the pieces.
• Remove Nth node from the back of the LL also needs the node at a fixed distance from the end.