How do you solve Rotate List on LeetCode?

Rotate List (LeetCode #61) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding effective rotations (k % length)

What is the brute force solution for Rotate List?

The brute force approach for Rotate List is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves rotating the list by moving nodes one by one. This is simple to understand but inefficient for larger lists. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Rotate List?

Rotate List uses the following concepts: Linked List, Two Pointers. The recommended patterns to study are: Two Pointers, Linked List Manipulation.

What are the interview tips for Rotate List?

Always consider edge cases like empty lists or k = 0 Explain your thought process clearly while coding Optimize your solution after implementing the brute-force approach

What are common mistakes when solving Rotate List?

Not handling the case where k is larger than the list length Forgetting to set the new tail's next to null

#61

Rotate List

Medium

Linked ListTwo PointersTwo PointersLinked List Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution involves finding the length of the list and adjusting the pointers to achieve the rotation in a single pass.

⚙️

Algorithm

4 steps

1Step 1: Calculate the length of the linked list and find the effective rotations needed (k % length).
2Step 2: If k is 0, return the head as no rotation is needed.
3Step 3: Traverse to the (length - k)th node to find the new tail and set its next to null.
4Step 4: Set the next of the new tail to the original head and update the head to the (length - k + 1)th node.

solution.py26 lines

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6def rotateRight(head, k):
7    if not head or not head.next or k == 0:
8        return head
9    n = 0
10    current = head
11    while current:
12        n += 1
13        current = current.next
14    k = k % n
15    if k == 0:
16        return head
17    tail = head
18    for _ in range(n - 1):
19        tail = tail.next
20    tail.next = head
21    new_tail = head
22    for _ in range(n - k - 1):
23        new_tail = new_tail.next
24    head = new_tail.next
25    new_tail.next = None
26    return head

ℹ

Complexity note: This complexity is O(n) because we traverse the list to find its length and then again to find the new tail. We only use a constant amount of extra space.

1Understanding effective rotations (k % length)
2Identifying the new head and tail efficiently

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.