Reverse Linked List

📋

Problem

Imagine you have a train of connected carriages and you want to reverse their order without detaching them all at once. This problem is about reversing the order of nodes in a linked list in-place.

Given the head of a singly linked list, reverse the list and return the reversed list's head.

The number of nodes in the list is in the range [1, 10^5].Node values can be any integer.You must reverse the list in-place with O(1) extra memory.

Edge cases: Single node list → output is the same single nodeTwo node list → nodes swappedList with all nodes having the same value → reversed list looks identical but pointers reversed

</>

IDE

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:public ListNode reverseList(ListNode head)ListNode* reverseList(ListNode* head)function reverseList(head)

def reverseList(head):
    # Write your solution here
    pass

class Solution {
    public ListNode reverseList(ListNode head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* reverseList(ListNode* head) {
    // Write your solution here
    return nullptr;
}

function reverseList(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 2, 3, 4, 5]Did not reverse the list at all; returned original head without pointer changes.✅ Implement pointer reversal logic using prev, curr, next pointers.

Wrong: [5, 4, 3, 2, 1] but with cycles causing infinite loopDid not set original head.next to None after reversal, causing cycles.✅ After reversal, set head.next = None to terminate the list.

Wrong: [5, 4, 3, 2, 1] but only values swapped, not pointersSwapped node values instead of reversing pointers.✅ Reverse node.next pointers instead of swapping node.val.

Wrong: Stack overflow or timeout on large inputUsed recursive approach causing stack overflow or exponential time.✅ Use iterative pointer reversal with O(1) space and O(n) time.

✓

Test Cases

Try testing your code on smallest lists and identical values to catch base case bugs.

Think about common mistakes like swapping values instead of pointers or recursion pitfalls.

Optimize your solution to run in O(n) time and O(1) space without recursion.

t1_01basic

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

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

⏱ Performance - must finish in 2000ms

Starting from 1->2->3->4->5, after reversal the list becomes 5->4->3->2->1.

💡 Think about how to reverse pointers one by one while traversing the list.

💡 Use three pointers: prev, curr, and next to reverse links iteratively.

💡 Set curr.next to prev in each iteration and move pointers forward.

Why it failed: Output incorrect - likely did not reverse pointers correctly or forgot to update next pointers. Fix by using prev, curr, next pointers and updating curr.next = prev each step.

✓ Correct reversal of pointers and list order confirmed.

t1_02basic

Input{"head":[10,20,30]}

Expected[30,20,10]

⏱ Performance - must finish in 2000ms

Reversing 10->20->30 results in 30->20->10.

💡 Try iterating through the list and reversing links one by one.

💡 Remember to keep track of the next node before changing curr.next.

💡 Return the last node processed as the new head after reversal.

Why it failed: Output incorrect - possibly lost track of next node or did not update head after reversal. Fix by saving next node before pointer reversal and returning new head.

✓ List reversed correctly with proper pointer updates.

t2_01edge

Input{"head":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node list reversed is the same single node.

💡 Check how your code handles lists with only one node.

💡 Make sure you return the head immediately if next is None.

💡 No pointer changes needed; just return the original head.

Why it failed: Failed single node case - likely did not handle base case where head.next is None. Fix by returning head immediately if head.next is None.

✓ Single node list handled correctly without unnecessary changes.

t2_02edge

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

Expected[2,1]

⏱ Performance - must finish in 2000ms

Two node list reversed swaps the two nodes.

💡 Test your reversal logic on the smallest multi-node list.

💡 Ensure pointers between the two nodes are swapped correctly.

💡 After reversal, the second node should point to the first, and first should point to None.

Why it failed: Failed two node swap - likely did not update the first node's next to None after reversal. Fix by setting original head.next = None after reversal.

✓ Two node list reversed correctly with proper pointer updates.

t2_03edge

Input{"head":[7,7,7,7]}

Expected[7,7,7,7]

⏱ Performance - must finish in 2000ms

All nodes have the same value; reversed list looks identical but pointers reversed.

💡 Don't rely on node values to check correctness; focus on pointer reversal.

💡 Verify that the last node in original list becomes the new head.

💡 Ensure each node's next pointer is reversed properly regardless of values.

Why it failed: Failed identical values case - likely compared values only and did not reverse pointers. Fix by reversing pointers explicitly, not just values.

✓ Pointers reversed correctly even when node values are identical.

t3_01corner

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

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

⏱ Performance - must finish in 2000ms

Greedy approach fails if you try to reverse values instead of pointers; correct reversal requires pointer manipulation.

💡 Avoid just swapping node values; focus on reversing links.

💡 Check if your code changes node.next pointers rather than node.val.

💡 Fix by implementing pointer reversal logic instead of value swapping.

Why it failed: Output incorrect - reversed values but not pointers. This is the greedy trap test. Fix by reversing node.next pointers, not node.val.

✓ Correct pointer reversal, not just value swapping.

t3_02corner

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

Expected[3,2,1]

⏱ Performance - must finish in 2000ms

Recursive approach must handle base case properly; forgetting to set head.next = None causes cycles.

💡 Check if your recursive reversal sets head.next to None after recursion.

💡 Ensure no cycles are created by old pointers still referencing nodes.

💡 Fix by setting head.next = None after recursive call returns.

Why it failed: Output incorrect - cycle or infinite loop due to not nullifying head.next after recursion. This is the recursive base case fix test.

✓ Recursive reversal correctly nullifies old next pointers.

t3_03corner

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

Expected[4,3,2,1]

⏱ Performance - must finish in 2000ms

Confusing iterative and recursive approaches can cause stack overflow or incorrect results.

💡 Verify your approach matches the problem constraints (in-place, O(1) space).

💡 Avoid using recursion for very large lists to prevent stack overflow.

💡 Fix by implementing iterative pointer reversal with three pointers.

Why it failed: Output incorrect or stack overflow - mixing recursive and iterative logic. This is the 0/1 vs unbounded recursion test. Fix by using iterative approach for large inputs.

✓ Iterative reversal correctly handles all input sizes without stack overflow.

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

Expectednull

⏱ Performance - must finish in 2000ms

Input list of length n=100; solution must run in O(n) time and O(1) space within 2 seconds.

💡 Use iterative reversal with constant extra space.

💡 Avoid recursion to prevent stack overflow on large inputs.

💡 Traverse the list once, reversing pointers in-place.

Why it failed: TLE or stack overflow due to recursive approach or non-linear complexity. Fix by using iterative O(n) pointer reversal.

✓ Efficient O(n) iterative reversal confirmed for large input.

Practice

1. 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

2. What is the time complexity of deleting a node in a singly linked list given only access to that node (no head pointer), using the optimal in-place approach that copies the next node's data and deletes the next node?

medium

A. O(n), because you need to traverse the list to find the node

B. O(1), because the operation only involves copying data and pointer updates

C. O(n), because you must recursively copy data from subsequent nodes

D. O(log n), because the deletion involves dividing the list

Solution

1. Step 1: Identify operations performed

   The algorithm copies the next node's value into the current node and updates the next pointer to skip the next node.

2. Step 2: Analyze time complexity

   These operations are constant time, no traversal or recursion is needed.

3. Step 3: Consider the initial access to the node

   However, if only the node to delete is given, no traversal is needed. But if only the value is given and node must be found, traversal is needed.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Copy and pointer update are O(1) operations [OK]

Hint: No traversal needed; only local pointer updates [OK]

Common Mistakes:

• Assuming traversal from head is needed, making it O(n)
• Confusing recursion with iterative approach
• Thinking deletion involves multiple node copies

3. What is the time complexity of the optimal min-heap based algorithm for merging k sorted linked lists with a total of N nodes?

medium

A. O(N k) because each node is compared with nodes from all k lists.

B. O(N log N) because all nodes are pushed and popped from the heap.

C. O(kN) because each list is merged sequentially with all others.

D. O(N log k) because each of the N nodes is pushed and popped from a heap of size at most k.

Solution

1. Step 1: Identify heap operations per node

   Each node is pushed and popped exactly once from a heap of size ≤ k.

2. Step 2: Calculate complexity

   Heap push/pop cost is O(log k), total O(N log k) for N nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap size depends on k, not N, so O(N log k) [OK]

Hint: Heap size is k, not N, so complexity is O(N log k) [OK]

Common Mistakes:

• Confusing N and k in log factor
• Assuming heap size grows with N
• Thinking sequential merges are optimal

4. What is the space complexity of the recursive approach to remove duplicates from a sorted linked list, and why might a common alternative answer be incorrect?

medium

A. O(1) because no extra data structures are used.

B. O(n) because a hash set is used to track duplicates.

C. O(log n) because the recursion depth is halved each call.

D. O(n) due to recursion stack space in the worst case.

Solution

1. Step 1: Identify recursion depth

   In the worst case, recursion proceeds one node at a time, leading to O(n) recursive calls on the stack.

2. Step 2: Analyze space usage

   No auxiliary data structures like hash sets are used, so extra space is only recursion stack space, which is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursive calls stack up to list length [OK]

Hint: Recursion stack space counts as extra space [OK]

Common Mistakes:

• Assuming O(1) space since no explicit data structures
• Confusing recursion depth with log n
• Thinking hash sets are used

5. Consider the following buggy code for swapping nodes in pairs in a linked list:

def swapPairs(head: ListNode) -> ListNode:
    def helper(node):
        if not node or not node.next:
            return node
        first = node
        second = node.next
        # Bug: missing update of first.next to recursive call
        second.next = first
        return second
    return helper(head)

What is the root cause of the bug?

medium

A. Returning second instead of first breaks the swapped pair order.

B. Assigning second.next before first.next causes pointer cycles.

C. Missing base case for empty list causes infinite recursion.

D. Not updating first.next to point to the result of recursive call causes lost nodes.

Solution

1. Step 1: Identify pointer updates in recursion

   The correct approach sets first.next = helper(second.next) to link swapped pairs recursively.

2. Step 2: Analyze missing update

   Without updating first.next, the rest of the list is disconnected, causing lost nodes after the first swapped pair.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing first.next update breaks list continuity [OK]

Hint: Always update first.next to recursive call result [OK]

Common Mistakes:

• Forgetting to link swapped pairs recursively
• Returning wrong node as new head