LeetCode 61 - Rotate List

This problem asks us to rotate a singly linked list to the right by k positions. A right rotation means that each node shifts one position toward the end of the list, and the last node wraps around to become the new head.

leetcodemediumlinked-listtwo-pointers

LeetCode Problem 61

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers

Solution

Problem Understanding

This problem asks us to rotate a singly linked list to the right by k positions. A right rotation means that each node shifts one position toward the end of the list, and the last node wraps around to become the new head.

For example, if the linked list is:

1 → 2 → 3 → 4 → 5

and we rotate it once to the right, the last element (5) moves to the front:

5 → 1 → 2 → 3 → 4

If we rotate it again, we get:

4 → 5 → 1 → 2 → 3

which matches Example 1 for k = 2.

The input consists of:

  • head, the head node of a singly linked list
  • k, the number of times to rotate the list to the right

The expected output is the head of the newly rotated linked list.

The constraints tell us several important things about the input size and behavior:

  • The linked list contains between 0 and 500 nodes, meaning the list is relatively small.
  • The rotation count k can be extremely large, up to 2 * 10^9.
  • Since k may be much larger than the list size, repeatedly rotating one step at a time would waste work.

An important observation is that rotating a list of length n by n positions produces the same list. Similarly, rotating by n + 1 is equivalent to rotating by 1. Therefore, only k % n actually matters.

There are several edge cases that can trip up a naive implementation:

  • An empty list (head = None) should immediately return None.
  • A single-node list never changes regardless of k.
  • k = 0 means no rotation should happen.
  • If k is a multiple of the list length, the result is unchanged.
  • Extremely large k values require modulo reduction to avoid unnecessary computation.

Approaches

Brute Force Approach

A straightforward solution is to simulate the rotation process one step at a time.

For each rotation:

  1. Traverse the list to find the second-to-last node.
  2. Remove the last node.
  3. Move the last node to the front.
  4. Repeat this process k times.

This works because every individual rotation correctly performs one right shift. Repeating it k times eventually produces the desired arrangement.

However, this approach is inefficient. Finding the last and second-to-last nodes requires traversing the list, which costs O(n) time per rotation. Repeating that k times results in O(n × k) complexity. Since k can be extremely large, up to 2 * 10^9, this solution becomes impractical.

Key Insight for an Optimal Solution

The crucial observation is that rotating by the list length does nothing.

If the list length is n, then:

k rotations ≡ k % n rotations

This drastically reduces unnecessary work.

Another useful insight is that instead of physically moving nodes one at a time, we can temporarily convert the linked list into a circular linked list.

For example:

1 → 2 → 3 → 4 → 5
              ↓
              ↑

If we connect the tail back to the head, the list becomes circular. Then we only need to determine:

  • where the new tail should be
  • where the new head should be

Once identified, we break the circle at the correct position.

This avoids repeated node movement and allows us to solve the problem in a single traversal.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × k) O(1) Rotate one step at a time by repeatedly moving the last node
Optimal O(n) O(1) Compute length, form a cycle, and break it at the correct position

Algorithm Walkthrough

Optimal Algorithm

  1. Handle trivial edge cases immediately

If the list is empty, contains only one node, or k == 0, return the original list. No rotation is necessary. 2. Compute the length of the linked list

Traverse the list while keeping track of:

  • the total number of nodes (length)
  • the last node (tail)

We need the length to reduce unnecessary rotations and the tail to create a circular list. 3. Reduce the rotation count

Compute:

k = k % length

Rotating by the list length produces the same list, so only the remainder matters. 4. Check whether rotation is still necessary

If k == 0, return the original head.

This happens when k is a multiple of the list length. 5. Create a circular linked list

Connect the tail to the head:

tail.next = head

This transforms the list into a cycle, allowing us to reposition the head efficiently. 6. Find the new tail

The new tail will be located at:

length - k - 1

steps from the current head.

Why? Because after rotation, the last k nodes move to the front, meaning the new tail sits right before those nodes. 7. Find the new head

The node immediately after the new tail becomes the new head:

new_head = new_tail.next
  1. Break the circular connection

Set:

new_tail.next = None

This restores the singly linked list structure. 9. Return the new head

The rotated list is now complete.

Why it works

The algorithm works because converting the list into a cycle preserves all node orderings while allowing rotation to become a pointer adjustment problem instead of repeated node movement.

After making the list circular, moving the head effectively means choosing a new breaking point. The node at position length - k - 1 must be the new tail because exactly k nodes need to move in front of it. Breaking the cycle there guarantees the resulting order matches a right rotation by k.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Edge cases
        if not head or not head.next or k == 0:
            return head

        # Find length and tail
        length = 1
        tail = head

        while tail.next:
            tail = tail.next
            length += 1

        # Reduce unnecessary rotations
        k %= length

        if k == 0:
            return head

        # Make circular list
        tail.next = head

        # Find new tail
        steps_to_new_tail = length - k - 1
        new_tail = head

        for _ in range(steps_to_new_tail):
            new_tail = new_tail.next

        # Set new head
        new_head = new_tail.next

        # Break cycle
        new_tail.next = None

        return new_head

The implementation begins by handling edge cases. If the list is empty, contains only one node, or no rotation is required, we immediately return the original list.

Next, we traverse the linked list once to compute its length and locate the tail node. These are both necessary for the optimized solution. The length allows us to reduce k using modulo arithmetic, while the tail is needed to temporarily form a circular linked list.

After reducing k, we check whether rotation is still required. If k % length == 0, the list remains unchanged.

The key step is connecting the tail back to the head to create a cycle. Once circular, we compute the position of the new tail as length - k - 1 steps from the current head. The node after this becomes the new head.

Finally, we break the cycle by setting new_tail.next = None, restoring the linked list structure and returning the rotated head.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k == 0 {
		return head
	}

	// Find length and tail
	length := 1
	tail := head

	for tail.Next != nil {
		tail = tail.Next
		length++
	}

	// Reduce unnecessary rotations
	k %= length

	if k == 0 {
		return head
	}

	// Make circular list
	tail.Next = head

	// Find new tail
	stepsToNewTail := length - k - 1
	newTail := head

	for i := 0; i < stepsToNewTail; i++ {
		newTail = newTail.Next
	}

	// Set new head
	newHead := newTail.Next

	// Break cycle
	newTail.Next = nil

	return newHead
}

The Go implementation closely mirrors the Python version. The main difference is handling nil pointers instead of Python's None. Go also uses explicit integer variables and for loops instead of Python's range syntax.

Since k ≤ 2 * 10^9, integer overflow is not an issue in Go because the standard int type comfortably handles values of this size on modern systems. Memory usage also remains constant because no extra data structures are allocated.

Worked Examples

Example 1

Input:

head = [1,2,3,4,5]
k = 2

Step 1: Compute Length

Variable Value
length 5
tail 5

Step 2: Reduce Rotations

k = 2 % 5 = 2

Step 3: Create Circular List

1 → 2 → 3 → 4 → 5
↑                 ↓
└─────────────────┘

Step 4: Find New Tail

We calculate:

length - k - 1 = 5 - 2 - 1 = 2

Move 2 steps from head:

Step Current Node
Start 1
1 2
2 3

New tail = 3

Step 5: Determine New Head

new_head = 4

Step 6: Break the Cycle

Final list:

4 → 5 → 1 → 2 → 3

Output:

[4,5,1,2,3]

Example 2

Input:

head = [0,1,2]
k = 4

Step 1: Compute Length

Variable Value
length 3
tail 2

Step 2: Reduce Rotations

k = 4 % 3 = 1

Step 3: Create Circular List

0 → 1 → 2
↑       ↓
└───────┘

Step 4: Find New Tail

length - k - 1 = 3 - 1 - 1 = 1

Move one step:

Step Current Node
Start 0
1 1

New tail = 1

Step 5: Determine New Head

new_head = 2

Step 6: Break the Cycle

Final list:

2 → 0 → 1

Output:

[2,0,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) One traversal computes length and another partial traversal finds the new tail
Space O(1) Only a few pointers and variables are used

Although there are technically two traversals, they are sequential and each visits at most n nodes, so the total work remains linear. No auxiliary data structures are allocated, meaning the algorithm uses constant extra memory.

Test Cases

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def linked_list_to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

solution = Solution()

# Example 1
head = build_list([1, 2, 3, 4, 5])
result = solution.rotateRight(head, 2)
assert linked_list_to_list(result) == [4, 5, 1, 2, 3]  # Standard rotation case

# Example 2
head = build_list([0, 1, 2])
result = solution.rotateRight(head, 4)
assert linked_list_to_list(result) == [2, 0, 1]  # k > length

# Empty list
head = build_list([])
result = solution.rotateRight(head, 3)
assert linked_list_to_list(result) == []  # Empty input

# Single node
head = build_list([1])
result = solution.rotateRight(head, 99)
assert linked_list_to_list(result) == [1]  # Single element unchanged

# No rotation
head = build_list([1, 2, 3])
result = solution.rotateRight(head, 0)
assert linked_list_to_list(result) == [1, 2, 3]  # k = 0

# Multiple of length
head = build_list([1, 2, 3, 4])
result = solution.rotateRight(head, 8)
assert linked_list_to_list(result) == [1, 2, 3, 4]  # k % length == 0

# Rotate by one
head = build_list([1, 2, 3])
result = solution.rotateRight(head, 1)
assert linked_list_to_list(result) == [3, 1, 2]  # Basic right shift

# Two nodes
head = build_list([1, 2])
result = solution.rotateRight(head, 1)
assert linked_list_to_list(result) == [2, 1]  # Small list edge case
Test Why
[1,2,3,4,5], k=2 Validates standard rotation
[0,1,2], k=4 Ensures modulo reduction works
[], k=3 Verifies empty list handling
[1], k=99 Tests single-node edge case
[1,2,3], k=0 Ensures no rotation happens
[1,2,3,4], k=8 Verifies multiple-of-length rotations
[1,2,3], k=1 Tests single right shift
[1,2], k=1 Smallest non-trivial list

Edge Cases

Empty List

An empty linked list is an important edge case because there are no nodes to rotate. A naive implementation that immediately traverses the list could trigger a null pointer error. The implementation avoids this by checking if not head at the start and returning immediately.

Single-Node List

When the list contains only one node, any number of rotations produces the exact same list. Without an early return, the algorithm could unnecessarily form a circular link or attempt invalid pointer movement. The implementation handles this safely with if not head.next.

Rotation Count Larger Than the List Length

Since k can be extremely large, repeatedly rotating would be prohibitively slow. For example:

[1,2,3], k = 1,000,000

Since the list length is 3, only:

1,000,000 % 3 = 1

actually matters. The modulo operation prevents wasted computation and keeps the solution efficient.

Rotation Count Equal to a Multiple of Length

If k is exactly divisible by the list length, the list should remain unchanged. For example:

[1,2,3], k = 6

Since:

6 % 3 = 0

no effective rotation occurs. The implementation explicitly checks k == 0 after modulo reduction and returns the original list immediately.