목록 회전

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

Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Solution

Let’s observe:

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

Enter fullscreen mode Exit fullscreen mode

After rotation:

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

Enter fullscreen mode Exit fullscreen mode

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;

Enter fullscreen mode Exit fullscreen mode

Rotating by n positions gives the same list.

Example:

n = 5
k = 7

7 % 5 = 2

Enter fullscreen mode Exit fullscreen mode

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;

Enter fullscreen mode Exit fullscreen mode

Step 3

Make the linked list circular

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

Enter fullscreen mode Exit fullscreen mode

Step 4

Find the new tail

newTailIndex = len - k - 1;

Enter fullscreen mode Exit fullscreen mode

Step 5

The node after newTail becomes newHead.

Step 6

Break the circle

newTail.next = null;

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

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

Enter fullscreen mode Exit fullscreen mode

Length

len = 5

Enter fullscreen mode Exit fullscreen mode

Effective Rotations

k = 2 % 5 = 2

Enter fullscreen mode Exit fullscreen mode

Make Circular

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

Enter fullscreen mode Exit fullscreen mode

Find New Tail

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

Enter fullscreen mode Exit fullscreen mode

Node at index 2:

3

Enter fullscreen mode Exit fullscreen mode

New Head

4

Enter fullscreen mode Exit fullscreen mode

Break Circle

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

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

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.