Reverse Linked List II (Sublist)

📋

Reverse Linked List II (Sublist)

Edge cases:

</>

IDE

def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:public ListNode reverseBetween(ListNode head, int left, int right)ListNode* reverseBetween(ListNode* head, int left, int right)function reverseBetween(head, left, right)

def reverseBetween(head, left, right):
    # Write your solution here
    pass

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* reverseBetween(ListNode* head, int left, int right) {
    // Write your solution here
    return nullptr;
}

function reverseBetween(head, left, right) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 3, 2, 4, 5]Reversed only one node or swapped nodes incorrectly; off-by-one error in sublist boundaries.✅ Adjust loop to reverse all nodes from left to right inclusive, not just one or two nodes.

Wrong: [5, 4, 3, 2, 1]Reversed entire list when only sublist should be reversed; left and right boundaries ignored.✅ Use pointers to isolate sublist between left and right and reverse only that segment.

Wrong: [1, 2, 3, 4, 5]No reversal performed when left != right; missing reversal logic.✅ Implement reversal logic for sublist when left != right; do not return original list prematurely.

Wrong: [1, 2, 3, 5, 4, 6]Incorrect reconnection after reversal; sublist tail pointer not updated properly.✅ After reversal, connect sublist tail's next pointer to the node after right.

Wrong: Timeout or crash on large inputInefficient algorithm with O(n^2) or worse complexity causing TLE.✅ Use O(n) in-place reversal algorithm without extra traversals or recursion depth issues.

✓

Test Cases

Now that basics are done, focus on edge cases like empty or single-node lists.

Next, test your code against tricky corner cases that expose off-by-one and pointer bugs.

Finally, optimize your solution to handle large inputs efficiently.

t1_01basic

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

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

⏱ Performance - must finish in 2000ms

Only the sublist from position 2 to 4 is reversed, so nodes 2,3,4 become 4,3,2.

💡 Focus on reversing only the sublist between left and right positions.

💡 Use pointer manipulation to reverse the sublist in-place without extra space.

💡 Detach the sublist, reverse it, then reconnect it back to the main list.

Why it failed: Failed to reverse the sublist correctly; likely did not isolate or reconnect the sublist properly. Fix by carefully detaching the sublist and reconnecting after reversal.

✓ Correctly reversed the sublist in-place preserving the rest of the list.

t1_02basic

Input{"head":[1,2,3,4,5,6],"left":1,"right":3}

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

⏱ Performance - must finish in 2000ms

The sublist from position 1 to 3 is reversed, so nodes 1,2,3 become 3,2,1.

💡 Remember to handle the case when the sublist starts at the head.

💡 Use a dummy node to simplify edge cases involving the head.

💡 After reversal, update the dummy's next pointer to the new head of the list.

Why it failed: Incorrect handling of sublist starting at head; likely did not use a dummy node or update head pointer. Fix by adding a dummy node and updating its next pointer after reversal.

✓ Successfully reversed sublist starting at head with proper pointer updates.

t2_01edge

Input{"head":[],"left":1,"right":1}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list input should return empty list regardless of left and right values.

💡 Check if the input list is empty before processing.

💡 Return the head immediately if it is None or empty.

💡 No reversal needed when list is empty.

Why it failed: Code crashes or returns non-empty output on empty input; fix by adding a check for empty list at start.

✓ Correctly handles empty list input by returning empty list.

t2_02edge

Input{"head":[1],"left":1,"right":1}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node list with left == right means no change to the list.

💡 If left equals right, no reversal is needed.

💡 Return the original list immediately in this case.

💡 Avoid unnecessary pointer manipulation when sublist length is 1.

Why it failed: Incorrectly modifies single node list when left == right; fix by returning head immediately if left == right.

✓ Correctly returns single node list unchanged when left == right.

t2_03edge

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

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

⏱ Performance - must finish in 2000ms

Reversing the entire list from position 1 to 5 reverses all nodes.

💡 Handle the case where the entire list is reversed.

💡 Use a dummy node to simplify head pointer updates.

💡 After reversal, dummy.next should point to the new head.

Why it failed: Failed to reverse entire list correctly; likely did not update head pointer after reversal. Fix by using dummy node and updating dummy.next.

✓ Successfully reversed entire list with proper pointer updates.

t2_04edge

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

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

⏱ Performance - must finish in 2000ms

Sublist length 1 at the end of the list means no change.

💡 Check if left equals right and return head immediately.

💡 No reversal needed for sublist length 1.

💡 Ensure tail pointer remains correct after no-op reversal.

Why it failed: Incorrectly modifies list when reversing single node at end; fix by returning head if left == right.

✓ Correctly returns list unchanged when sublist length is 1 at tail.

t3_01corner

Input{"head":[1,2,3,4,5,6],"left":3,"right":5}

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

⏱ Performance - must finish in 2000ms

Reversing sublist in the middle; tests correct pointer reconnection after reversal.

💡 Check that nodes before left and after right remain unchanged.

💡 Ensure the sublist is reversed in-place without affecting other nodes.

💡 Reconnect the reversed sublist correctly to the nodes before and after.

Why it failed: Incorrect reconnection of reversed sublist; likely pointers before or after sublist not updated. Fix by carefully linking prevLeft.next and sublist_tail.next.

✓ Correctly reverses middle sublist and reconnects list.

t3_02corner

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

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

⏱ Performance - must finish in 2000ms

Sublist length is 1 (left == right), so list remains unchanged.

💡 Check if left equals right and return head immediately.

💡 Avoid reversing when sublist length is 1.

💡 This test catches off-by-one errors in sublist length calculation.

Why it failed: Incorrectly modifies list when left == right; fix by adding condition to return head if left == right.

✓ Correctly returns list unchanged when sublist length is 1.

t3_03corner

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

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

⏱ Performance - must finish in 2000ms

Reversing sublist at the end of the list; tests correct tail pointer update.

💡 Ensure the tail pointer is updated after reversing the sublist at the end.

💡 Check that the last node's next pointer is set to None after reversal.

💡 Reconnect the reversed sublist properly to the rest of the list.

Why it failed: Tail pointer not updated correctly after reversing end sublist; fix by setting sublist_head.next to afterRight (which may be None).

✓ Successfully reversed end sublist with correct tail pointer update.

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],"left":1,"right":100}

Expectednull

⏱ Performance - must finish in 2000ms

Reversing entire list of length 100; O(n) time complexity must complete within 2 seconds.

💡 Use an O(n) in-place reversal algorithm.

💡 Avoid extra space or nested loops to prevent TLE.

💡 Iterate through the list once to reverse the sublist.

Why it failed: Solution exceeds time limit due to O(n^2) or worse complexity; fix by implementing O(n) in-place reversal.

✓ Solution runs within time limit using O(n) in-place reversal.

Practice

1. Given the following Python code implementing the optimal recursive addition of two linked lists representing numbers in forward order, what is the value of the carry returned by addListsHelper when adding lists representing 724 and 564?

easy

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Trace addition from least significant digit

   Adding 4 + 4 = 8, carry 0; next 2 + 6 = 8, carry 0; finally 7 + 5 = 12, carry 1.

2. Step 2: Propagate carry backward

   Carry 1 is returned from the most significant digit addition, indicating an overflow digit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   724 + 564 = 1288, carry 1 at MSB addition [OK]

Hint: Carry is from MSB addition overflow [OK]

Common Mistakes:

• Ignoring carry from most significant digit
• Off-by-one error in recursion base case
• Misaligning lists before addition

2. Given the following recursive code for swapping nodes in pairs, what is the output when the input list is 1 -> 2 -> 3 -> null?

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

def swapPairs(head: ListNode) -> ListNode:
    def helper(node):
        if not node or not node.next:
            return node
        first = node
        second = node.next
        first.next = helper(second.next)
        second.next = first
        return second
    return helper(head)

# Input list: 1 -> 2 -> 3 -> null

What is the printed output after swapping pairs?

easy

A. 2 3 1

B. 1 3 2

C. 2 1 3

D. 3 2 1

Solution

1. Step 1: Trace helper on node with val=1

   First = 1, Second = 2; recursively call helper on node with val=3.

2. Step 2: Trace helper on node with val=3

   Node 3 has no next, so return node 3 as is.

3. Step 3: Complete first call

   Set first.next = node 3, second.next = first (1), return second (2). Resulting list: 2 -> 1 -> 3.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Output matches expected swapped pairs [OK]

Hint: Recursive swaps pairs, last odd node remains [OK]

Common Mistakes:

• Swapping values instead of nodes
• Misplacing last node in odd-length list

3. What is the space complexity of the iterative in-place linked list addition algorithm that reuses input nodes to store the sum?

medium

A. O(max(m, n)) due to creating new nodes for sum digits

B. O(m + n) because it stores carry in a separate list

C. O(1) additional space since it modifies input lists in-place

D. O(log(max(m, n))) due to recursion stack overhead

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm modifies one input list in-place and only uses a few variables for carry and pointers.

2. Step 2: Confirm no extra list or recursion stack

   No new list nodes are created except possibly one if carry remains, which is constant extra space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   In-place modification means constant extra space [OK]

Hint: In-place means O(1) extra space, not O(n) [OK]

Common Mistakes:

• Confusing input list size with extra space
• Assuming recursion stack space applies here
• Thinking carry requires extra list storage

4. Consider the following buggy code snippet for removing duplicates from a sorted linked list. Which line contains the subtle bug that causes incorrect removal of duplicates at the head of the list?

def deleteDuplicates(head):
    if not head or not head.next:
        return head
    prev = None
    current = head
    while current and current.next:
        if current.val == current.next.val:
            val_to_remove = current.val
            while current and current.val == val_to_remove:
                current = current.next
            if prev:
                prev.next = current
        else:
            prev = current
            current = current.next
    return head

medium

A. Line 3: prev initialized to null instead of dummy node.

B. Line 7: while loop condition should check current.next.val instead of current.val.

C. Line 11: Missing update of prev when duplicates are removed at head.

D. Line 14: prev pointer updated incorrectly inside else block.

Solution

1. Step 1: Identify problem with head duplicates

   Without a dummy node, if duplicates appear at the head, prev is None and cannot link to the new head after removal.

2. Step 2: Analyze code behavior

   Line 3 initializes prev to None instead of a dummy node, so when duplicates at the head are removed, the head pointer is not updated correctly, causing incorrect output.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Dummy node needed to handle head duplicates [OK]

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

Common Mistakes:

• Not using dummy head
• Incorrect prev updates
• Skipping null checks

5. Suppose you want to reverse a singly linked list that may contain cycles (i.e., some node's next pointer points to a previous node). Which modification to the standard tail-recursive reversal algorithm correctly handles this scenario without infinite recursion?

hard

A. Add a visited set to track nodes already reversed and stop recursion if a node repeats.

B. Use the standard tail-recursive reversal without changes; cycles will be reversed naturally.

C. Convert the list to an array first, then reverse the array and rebuild the list to avoid cycles.

D. Limit recursion depth to a fixed number to prevent infinite loops in cycles.

Solution

1. Step 1: Understand cycle problem

   Standard reversal assumes acyclic list; cycles cause infinite recursion or loops.

2. Step 2: Modify algorithm

   Tracking visited nodes prevents revisiting and infinite recursion by stopping when a node repeats.

3. Step 3: Evaluate other options

   Standard recursion (B) fails on cycles. Converting to array (C) is inefficient and not in-place. Limiting recursion depth (A) is arbitrary and unsafe.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited set detects cycles and prevents infinite recursion [OK]

Hint: Detect cycles with visited set to avoid infinite recursion [OK]

Common Mistakes:

• Assuming input list is always acyclic
• Ignoring cycle detection in recursive reversal