Swap Nodes in Pairs

📋

Problem

Imagine you have a chain of train cars, and you want to swap every two adjacent cars to optimize loading. How would you do this efficiently without detaching the entire chain?

Given a singly linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed). Input: head of the linked list. Output: head of the modified list after swapping every two adjacent nodes.

The number of nodes in the list is in the range [1, 10^5].1 ≤ Node.val ≤ 1000

Edge cases: Empty list → returns empty listSingle node list → returns same single nodeList with odd number of nodes → last node remains in place

</>

IDE

def swapPairs(head: ListNode) -> ListNode:public ListNode swapPairs(ListNode head)ListNode* swapPairs(ListNode* head)function swapPairs(head)

def swapPairs(head: ListNode) -> ListNode:
    # Write your solution here
    pass

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: [1,2,3,4]No swapping performed; code returns original list.✅ Implement swapping logic by changing node pointers for every pair.

Wrong: [2,1,3,4]Only first pair swapped; rest of list unchanged.✅ Recursively or iteratively continue swapping pairs throughout the list.

Wrong: [1]Code crashes or returns empty on single node input.✅ Add base case to return head if head.next is None.

Wrong: [1,2,3]Last node swapped incorrectly or lost in odd-length list.✅ Stop swapping when fewer than two nodes remain.

Wrong: [1,2]Swapped node values instead of nodes.✅ Swap nodes by changing next pointers, not node values.

✓

Test Cases

Focus on handling empty and minimal input cases correctly.

Think about common pitfalls like greedy swaps and pointer mismanagement.

Optimize your solution to run efficiently on large inputs.

t1_01basic

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

Expected[2,1,4,3]

⏱ Performance - must finish in 2000ms

Swap nodes 1 and 2, then nodes 3 and 4.

💡 Think about swapping pairs of nodes in the linked list.

💡 Use recursion or iteration to swap every two adjacent nodes.

💡 Swap first two nodes, then recursively swap the rest.

Why it failed: Output does not match expected swapped pairs. Likely missed swapping pairs or incorrect pointer updates. Fix by ensuring each pair of nodes is swapped and linked correctly.

✓ Correctly swaps every two adjacent nodes as expected.

t1_02basic

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

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

⏱ Performance - must finish in 2000ms

Swap nodes in pairs: (1,2), (3,4), (5,6).

💡 Extend the swapping logic to longer lists with even length.

💡 Ensure the swapping continues until the end of the list.

💡 After swapping a pair, link to the result of swapping the rest.

Why it failed: Output incorrect due to incomplete swapping or wrong linking after pairs. Fix by recursively or iteratively swapping all pairs and linking properly.

✓ Successfully swaps all pairs in the list.

t2_01edge

Input{"head":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list returns empty list.

💡 Check how your code handles an empty input list.

💡 Make sure to return immediately if head is None.

💡 Return head as is when list is empty.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding base case: if head is None, return None.

✓ Correctly handles empty list input.

t2_02edge

Input{"head":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node list returns same single node.

💡 Consider the case when list has only one node.

💡 No pairs to swap, so return head as is.

💡 Add base case: if head.next is None, return head.

Why it failed: Swapping attempted on single node causing errors or wrong output. Fix by returning head if head.next is None.

✓ Correctly returns single node list unchanged.

t2_03edge

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

Expected[2,1,3]

⏱ Performance - must finish in 2000ms

Odd number of nodes: last node remains in place.

💡 When list length is odd, last node is not swapped.

💡 Ensure swapping stops when fewer than two nodes remain.

💡 Check base case for recursion or loop termination condition.

Why it failed: Last node incorrectly swapped or lost. Fix by stopping swaps when less than two nodes remain.

✓ Correctly leaves last node in place for odd-length list.

t3_01corner

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

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

⏱ Performance - must finish in 2000ms

Greedy trap: swapping nodes greedily without proper linking causes errors.

💡 Beware of swapping nodes greedily without updating next pointers correctly.

💡 Use a dummy node or recursion to maintain correct links after swaps.

💡 Fix by carefully updating next pointers after each pair swap.

Why it failed: Output incorrect due to greedy swapping without proper pointer updates. Fix by using dummy node or recursion to maintain links.

✓ Correctly handles swapping with proper pointer updates.

t3_02corner

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

Expected[2,1]

⏱ Performance - must finish in 2000ms

0/1 confusion: swapping nodes vs swapping values.

💡 Do not swap node values; swap nodes themselves.

💡 Ensure you update node.next pointers, not just values.

💡 Fix by swapping nodes by changing pointers, not values.

Why it failed: Output incorrect because values swapped instead of nodes. Fix by swapping node pointers, not node values.

✓ Correctly swaps nodes, not just values.

t3_03corner

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

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

⏱ Performance - must finish in 2000ms

Off-by-one error: last node in odd-length list must remain unchanged.

💡 Check loop or recursion termination conditions carefully.

💡 Ensure you do not swap when fewer than two nodes remain.

💡 Fix by adding condition to stop swapping when next node is None.

Why it failed: Last node incorrectly swapped or lost due to off-by-one error. Fix by adding proper termination condition.

✓ Correctly handles odd-length list with last node unchanged.

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

n=100 nodes, O(n) time complexity expected to complete within 2 seconds.

💡 Algorithm should run in linear time O(n).

💡 Avoid recursion depth issues by using iterative approach.

💡 Use dummy node and iteration to achieve O(n) time and O(1) space.

Why it failed: Solution times out due to exponential or quadratic complexity. Fix by implementing O(n) iterative or tail-recursive solution.

✓ Solution runs within time limit confirming O(n) complexity.

Practice

1. You are given a sorted singly linked list and need to remove all duplicate nodes so that each element appears only once. Which approach guarantees an optimal in-place solution with linear time complexity and constant extra space?

easy

A. Use a hash set to track seen values and remove duplicates by reconstructing the list.

B. Use a nested loop to compare each node with all subsequent nodes and remove duplicates.

C. Iterate once through the list, comparing each node with its next node and removing duplicates in-place.

D. Sort the list first, then remove duplicates by scanning through it.

Solution

1. Step 1: Understand the problem constraints

   The list is already sorted, so duplicates appear consecutively, allowing a single pass to remove them efficiently.

2. Step 2: Identify the optimal approach

   Iterating once and comparing each node with its next node lets us remove duplicates in-place with O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with pointer manipulation matches optimal solution [OK]

Hint: Sorted list allows single pass duplicate removal [OK]

Common Mistakes:

• Thinking nested loops are needed despite sorted input

2. You are given a singly linked list and an integer n. The task is to remove the n-th node from the end of the list in one pass without using extra space. Which approach guarantees this with optimal time and space complexity?

easy

A. Use two pointers spaced n nodes apart to find and remove the target node in one pass.

B. Traverse the list twice: first to count nodes, second to remove the target node.

C. Use dynamic programming to store intermediate results for node positions.

D. Sort the list first, then remove the node based on sorted order.

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing the n-th node from the end in one pass without extra space.

2. Step 2: Evaluate approaches

   Two pointers spaced n apart allow traversal in one pass, identifying the node to remove without counting or extra storage.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer technique is classic for single-pass linked list problems [OK]

Hint: Two pointers spaced n apart find target in one pass [OK]

Common Mistakes:

• Thinking two passes are necessary
• Using extra space for indexing
• Misapplying DP to linked list traversal

3. What is the space complexity of the recursive approach to remove the nth node from the end of a singly linked list of length n?

medium

A. O(1) -- constant extra space since no data structures are used

B. O(n) -- due to recursion stack frames for each node

C. O(log n) -- recursion depth is logarithmic due to divide and conquer

D. O(n) -- due to auxiliary arrays used to store node references

Solution

1. Step 1: Identify recursion depth

   Recursion visits each node once, so recursion stack depth is n.

2. Step 2: Analyze space usage

   No extra arrays or data structures are used, but recursion stack frames consume O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack space grows linearly with list length [OK]

Hint: Recursion stack space equals max call depth [OK]

Common Mistakes:

• Assuming constant space for recursion
• Confusing recursion with iterative approach
• Thinking recursion depth is logarithmic

4. Identify the bug in the following tail-recursive reversal code snippet:

def reverseList(head):
    def helper(prev, curr):
        if not curr:
            return prev
        curr.next = prev
        next_temp = curr.next
        return helper(curr, next_temp)
    return helper(None, head)

medium

A. Line 3: Base case should check if prev is None instead of curr.

B. Line 6: The recursive call should pass next_temp as prev instead of curr.

C. Line 5: next_temp is assigned after curr.next is changed, losing original next node.

D. Line 2: The helper function should be iterative, not recursive.

Solution

1. Step 1: Analyze pointer updates

   Line 5 assigns next_temp = curr.next after curr.next is set to prev, so next_temp points to prev, not the original next node.

2. Step 2: Consequence of bug

   Because next_temp is incorrect, recursion loses the rest of the list, causing incomplete reversal or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Saving next node before pointer reversal is critical [OK]

Hint: Always save next node before changing curr.next [OK]

Common Mistakes:

• Swapping order of pointer updates
• Forgetting to set head.next to None in recursion

5. Suppose you want to merge k sorted linked lists but now the lists can contain duplicate values and you want to return only the top M smallest unique values in sorted order. Which modification to the min-heap approach correctly achieves this?

hard

A. Use a min-heap and maintain a hash set to skip duplicates when extracting nodes, stopping after M unique values.

B. Use the same min-heap approach but stop after extracting M nodes, ignoring duplicates.

C. Merge all lists into one array, remove duplicates, sort, and return first M values.

D. Sequentially merge lists and remove duplicates during merge until M unique values are collected.

Solution

1. Step 1: Understand requirement for unique values

   Duplicates must be skipped, and only M unique smallest values returned.

2. Step 2: Modify min-heap approach

   Maintain a hash set to track seen values; when popping from heap, skip if duplicate; stop after M unique values.

3. Step 3: Why other options fail

   Stopping after M nodes ignores duplicates; merging all nodes wastes time and space; sequential merges are inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash set + min-heap ensures unique sorted extraction efficiently [OK]

Hint: Use hash set with min-heap to filter duplicates on the fly [OK]

Common Mistakes:

• Stopping after M nodes without filtering duplicates
• Sorting all nodes wastes time
• Sequential merges inefficient for large k