Rotate List

Linked Lists keep finding new ways to test pointer manipulation. Today's problem looks simple at first glance, but the optimal solution comes from a powerful observation: instead of moving nodes one by one, convert the list into a circle and break it at the correct position.

Problem Statement

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

Example

Input:
1 -> 2 -> 3 -> 4 -> 5
k = 2

Output:
4 -> 5 -> 1 -> 2 -> 3

Brute Force Intuition

A straightforward approach is:

Find the last node.
Remove it.
Insert it at the beginning.
Repeat this process k times.

For every rotation, we traverse almost the entire list to find the last node.

Interview Explanation

For each rotation, we move the last node to the front. Since finding the last node takes O(n), and we do this k times, the overall complexity becomes O(n × k), which is inefficient when k is large.

Complexity

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

Moving Towards the Optimal Solution

Let's observe:

1 -> 2 -> 3 -> 4 -> 5
k = 2

After rotation:

4 -> 5 -> 1 -> 2 -> 3

Instead of physically rotating nodes one by one:

Find the length of the list.
Connect the tail to the head.
The list becomes circular.
Find the new tail.
Break the circle.

This transforms the problem into finding the correct breaking point.

Key Observation

If the list length is n:

k = k % n;

Rotating by n positions gives the same list.

Example:

n = 5
k = 7

7 % 5 = 2

Rotating by 7 is equivalent to rotating by 2.

Optimal Approach

Step 1

Find:

Length of the list
Tail node

Step 2

Reduce unnecessary rotations

k %= len;

Step 3

Make the linked list circular

1 -> 2 -> 3 -> 4 -> 5
^                   |
|___________________|

Step 4

Find the new tail

newTailIndex = len - k - 1;

Step 5

The node after newTail becomes newHead.

Step 6

Break the circle

newTail.next = null;

Dry Run

Input

1 -> 2 -> 3 -> 4 -> 5
k = 2

Length

len = 5

Effective Rotations

k = 2 % 5 = 2

Make Circular

1 -> 2 -> 3 -> 4 -> 5
^                   |
|___________________|

Find New Tail

len - k - 1
= 5 - 2 - 1
= 2

Node at index 2:

New Head

Break Circle

4 -> 5 -> 1 -> 2 -> 3

Answer obtained.

Optimal Java Solution

class Solution {

    public ListNode rotateRight(ListNode head, int k) {

        if (head == null || head.next == null)
            return head;

        int len = 1;
        ListNode tail = head;

        while (tail.next != null) {
            len++;
            tail = tail.next;
        }

        k %= len;

        if (k == 0)
            return head;

        // Make circular linked list
        tail.next = head;

        // Find new tail
        ListNode newTail = getNthNode(head, len - k - 1);

        // New head
        ListNode newHead = newTail.next;

        // Break circle
        newTail.next = null;

        return newHead;
    }

    private ListNode getNthNode(ListNode node, int index) {

        int count = 0;

        while (node != null) {

            if (count == index)
                return node;

            count++;
            node = node.next;
        }

        return null;
    }
}

Why This Works

After making the list circular, every possible rotation already exists inside the circle.

The only task left is identifying:

Where the new head should start.
Where the new tail should end.

Once the circle is broken at that point, the rotated list is formed automatically.

Complexity Analysis

Time  : O(n)

Space : O(1)

Only one traversal is required to compute length and locate the breaking point.

Pattern Recognition

Whenever you hear:

Rotate Linked List
Move last k nodes to front
Circular arrangement of nodes

Think:

Make the list circular → Find the new tail → Break the circle.

This is the standard O(n) Linked List rotation pattern asked in interviews.

Interview One-Liner

Instead of rotating nodes one by one, I connect the tail to the head to form a circular linked list, locate the new tail at (length - k - 1), and break the circle to obtain the rotated list in O(n) time and O(1) space.

推荐订阅源

DEV Community