Rotate List

📋

Problem

Imagine a conveyor belt of packages where the last few packages need to be moved to the front without rearranging the entire belt manually.

Given the head of a linked list and an integer k, rotate the list to the right by k places. Return the rotated list's head.

The number of nodes in the list is in the range [1, 10^5].0 ≤ k ≤ 10^9

Edge cases: Single node list → output same listk is zero → output same listk is multiple of list length → output same list

</>

IDE

def rotateRight(head: ListNode, k: int) -> ListNode:public ListNode rotateRight(ListNode head, int k)ListNode* rotateRight(ListNode* head, int k)function rotateRight(head, k)

def rotateRight(head, k):
    # Write your solution here
    pass

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* rotateRight(ListNode* head, int k) {
    // Write your solution here
    return nullptr;
}

function rotateRight(head, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 2, 3, 4, 5]Forgot to apply k modulo length, so rotation is skipped incorrectly.✅ Add k = k % length before rotation logic.

Wrong: [2, 3, 4, 5, 1]Off-by-one error in finding new tail; rotated one less than required.✅ Set new tail at length - k - 1 node, not length - k.

Wrong: [5, 1, 2, 3, 4, 6]Incorrectly breaking the list or not setting new tail's next to null.✅ After connecting tail to head, set new tail.next = null to break the ring.

Wrong: Timeout or no outputUsing repeated single rotations for large k causing O(n*k) complexity.✅ Use O(n) approach: compute length, k modulo length, connect tail to head, find new tail with two pointers, break ring.

✓

Test Cases

Focus on handling base cases like empty or single node lists and zero rotations.

Check pointer arithmetic carefully and test with large k values to avoid off-by-one and overflow errors.

Optimize your solution to O(n) by avoiding repeated rotations and using modulo arithmetic.

t1_01basic

Input{"head":[1,2,3,4,5],"k":2}

Expected[4,5,1,2,3]

⏱ Performance - must finish in 2000ms

Rotating the list by 2 moves the last two nodes to the front.

💡 Think about connecting the tail to the head to form a ring.

💡 Calculate the effective rotation by k modulo list length.

💡 Break the ring at the new tail to form the rotated list.

Why it failed: Failed to handle rotation correctly; likely missed modulo operation or ring formation. Fix by computing k = k % length and connecting tail to head before breaking at new tail.

✓ Correctly rotates list by k positions using ring formation and breaking.

t1_02basic

Input{"head":[0,1,2],"k":4}

Expected[2,0,1]

⏱ Performance - must finish in 2000ms

Rotating by 4 is equivalent to rotating by 1 (4 % 3 = 1), moving last node to front.

💡 Remember to use modulo to reduce k within list length.

💡 Use two pointers to find new tail and new head positions.

💡 Reconnect tail to head and break at new tail to rotate.

Why it failed: Incorrect rotation when k > length; likely forgot to modulo k by list length. Fix by adding k = k % length before rotation.

✓ Handles rotations larger than list length correctly.

t2_01edge

Input{"head":[1],"k":99}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node list rotated any number of times remains the same.

💡 Check if list has only one node or is empty.

💡 Rotation should return the same list if length <= 1.

💡 Add base case: if not head or not head.next, return head immediately.

Why it failed: Fails single node case by performing unnecessary rotations causing errors. Fix by adding base case to return head if list length is 1.

✓ Correctly handles single node list without changes.

t2_02edge

Input{"head":[1,2],"k":0}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Rotation by zero means list remains unchanged.

💡 Check if k is zero before processing.

💡 Return head immediately if k == 0.

💡 Add early return for k == 0 to avoid unnecessary computation.

Why it failed: Fails to handle k=0 by performing rotations unnecessarily. Fix by returning head immediately if k == 0.

✓ Correctly returns original list when k is zero.

t2_03edge

Input{"head":[1,2,3],"k":3}

Expected[1,2,3]

⏱ Performance - must finish in 2000ms

Rotation by list length results in the same list.

💡 Calculate k modulo length to handle full rotations.

💡 If k % length == 0, return head as is.

💡 Add condition to return head if k % length == 0.

Why it failed: Fails to handle k equal to list length; rotates unnecessarily. Fix by returning head if k % length == 0.

✓ Correctly returns original list when k is multiple of list length.

t3_01corner

Input{"head":[1,2,3,4,5],"k":1}

Expected[5,1,2,3,4]

⏱ Performance - must finish in 2000ms

Rotating by 1 moves last node to front; tests off-by-one errors in pointer manipulation.

💡 Use two pointers spaced k apart to find new tail.

💡 Ensure new tail is at length - k - 1 position.

💡 Break the list at new tail and reconnect properly.

Why it failed: Off-by-one error in finding new tail causes incorrect rotation. Fix by setting new tail at length - k - 1 node.

✓ Correctly handles off-by-one pointer positioning for rotation.

t3_02corner

Input{"head":[1,2,3,4,5],"k":5}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Rotation by list length should return original list; tests if code handles exact boundary correctly.

💡 Check if k modulo length equals zero.

💡 Return head immediately if no rotation needed.

💡 Avoid unnecessary pointer changes when k % length == 0.

Why it failed: Fails to detect no-op rotation when k equals list length. Fix by returning head if k % length == 0.

✓ Correctly returns original list when rotation equals list length.

t3_03corner

Input{"head":[1,2,3,4,5],"k":1000000000}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Very large k tests if modulo operation is used to reduce rotations.

💡 Always reduce k by modulo length to avoid large unnecessary rotations.

💡 Use k = k % length before processing.

💡 Without modulo, code will be inefficient or incorrect.

Why it failed: Fails large k input by not using modulo, causing timeouts or wrong output. Fix by computing k = k % length before rotation.

✓ Handles very large k efficiently using modulo.

t4_01performance

Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":1000000000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, k very large; O(n) solution must complete within 2 seconds.

💡 Avoid repeated single rotations (O(n*k)) which will time out.

💡 Use length calculation and modulo to reduce k.

💡 Use two-pointer technique to find new tail in O(n) time.

Why it failed: TLE due to O(n*k) brute force approach; fix by using O(n) approach with modulo and two pointers.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following Python code for merging two sorted linked lists in-place:

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

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            l1 = l1.next
        prev.next = l2
        l1, l2 = l2, l1
    return head

# Input lists:
# l1: 1 -> 3 -> 5
# l2: 2 -> 4

merged_head = mergeTwoLists(l1, l2)

What is the value of the node pointed to by prev after the first inner while loop iteration inside the outer while loop?

easy

A. Node with value 3

B. Node with value 5

C. Node with value 1

D. Node with value 2

Solution

1. Step 1: Trace the inner while loop with initial lists

   Initially, l1 points to 1, l2 points to 2. The inner loop advances l1 while l1.val <= l2.val: - l1=1 (<=2), prev=1, l1 moves to 3 - l1=3 (>2), loop stops

2. Step 2: Identify prev after loop

   Prev points to node with value 1 after the inner loop ends, which is the last node with value less than or equal to l2.val.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Prev points to last l1 node ≤ current l2 node [OK]

Hint: Prev points to last l1 node ≤ current l2 node [OK]

Common Mistakes:

• Assuming prev points to node with value 3 after first inner loop
• Confusing l1 and l2 pointers after swap
• Forgetting that prev updates inside inner loop

2. Consider the following code snippet that removes duplicates from a sorted linked list. Given the input list: 1 -> 1 -> 2, what is the output printed by the code?

easy

A. 1 1 2

B. 1 2

C. 2

D. 1

Solution

1. Step 1: Trace initial list and first iteration

   Start with current at first node (1). current.next is also 1, so duplicate detected; remove second node by linking current.next to current.next.next (node with value 2).

2. Step 2: Continue iteration

   Now current.next is 2, which differs from current.val (1), so move current to next node (2). current.next is None, loop ends.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Duplicates removed, final list is 1 -> 2 [OK]

Hint: Duplicates removed by skipping next pointer [OK]

Common Mistakes:

• Forgetting to move current pointer after removal

3. The following code attempts to merge two sorted linked lists in-place:

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            # BUG: Missing l1 pointer advancement here
        prev.next = l2
        l1, l2 = l2, l1
    return head

What is the bug in this code?

medium

A. Swapping l1 and l2 when l1.val > l2.val is incorrect

B. Not initializing prev before inner while loop causes NoneType error

C. Returning head instead of l1 or l2 at the end causes wrong output

D. Line missing advancement of l1 inside inner while loop causes infinite loop

Solution

1. Step 1: Identify the inner while loop behavior

   The inner loop should advance l1 pointer to traverse nodes with values <= l2.val. Missing l1 = l1.next causes infinite loop.

2. Step 2: Confirm impact of missing advancement

   Without advancing l1, prev remains the same, loop never ends, causing infinite loop or crash.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing l1 advancement inside inner loop causes infinite loop [OK]

Hint: Always advance pointers inside loops to avoid infinite loops [OK]

Common Mistakes:

• Confusing swap of l1 and l2 as bug
• Thinking return head is incorrect
• Assuming prev initialization causes error

4. Consider the following buggy code snippet for removing the nth node from the end of a linked list. Which line contains the subtle bug that causes incorrect behavior when removing the head node?

medium

A. Line 13: Wrong condition for node removal

B. Line 10: Incorrect base case for recursion

C. Line 5: Missing dummy node initialization

D. Line 15: Returning head instead of dummy.next

Solution

1. Step 1: Identify missing dummy node

   Without a dummy node, removing the head node causes pointer errors or incorrect list head.

2. Step 2: Check recursion call and return

   Recursion is called on head, but no dummy means no safe predecessor to update head pointer.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Dummy node is essential to handle head removal safely [OK]

Hint: Always use dummy node to handle head removal [OK]

Common Mistakes:

• Not using dummy node
• Incorrect recursion base case
• Returning wrong node after removal

5. Suppose the digits in the input linked lists are stored in forward order (most significant digit first). Which modification to the in-place iterative addition algorithm is necessary to correctly add the two numbers?

hard

A. Traverse both lists once, adding digits directly without reversing, handling carry forward.

B. Create new nodes for the sum since in-place modification is impossible with forward order.

C. Use recursion to add digits from head to tail, passing carry backward.

D. Reverse both input lists, apply the in-place addition, then reverse the result list back.

Solution

1. Step 1: Understand forward order challenge

   Digits stored most significant first require addition from tail to head to handle carry properly.

2. Step 2: Reverse input lists

   Reversing both lists converts them to reverse order, allowing reuse of the in-place addition algorithm.

3. Step 3: Reverse result list

   After addition, reverse the result to restore forward order.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reversing lists enables correct carry handling in forward order [OK]

Hint: Reverse lists to reuse reverse-order addition logic [OK]

Common Mistakes:

• Trying to add forward order lists without reversing
• Assuming carry can be handled left-to-right easily
• Creating new lists unnecessarily