Swap Nodes in Pairs

Difficulty: Medium | Acceptance: 67.77% | Paid: No

Topics: Linked List, Recursion

• Examples
• Constraints
• Brute Force - Array-based Swapping
• Recursive Approach
• Iterative Approach with Dummy Node

Examples

Example 1

Input:

head = [1,2,3,4]

Output:

[2,1,4,3]

Example 2

Input:

head = []

Output:

[]

Example 3

Input:

head = [1]

Output:

[1]

Example 4

Input:

head = [1,2,3]

Output:

[2,1,3]

Constraints

- The number of nodes in the list is in the range [0, 100].
- 0 <= Node.val <= 100

Brute Force - Array-based Swapping

Intuition

Convert the linked list into an array, perform swaps on the array, and reconstruct the linked list.

Steps

• Traverse the linked list and store all node values in an array.
• Iterate through the array and swap every pair of adjacent elements.
• Reconstruct the linked list from the modified array.

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

def swapPairs(head):
    if not head or not head.next:
        return head
    
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next
    
    for i in range(0, len(values) - 1, 2):
        values[i], values[i+1] = values[i+1], values[i]
    
    dummy = ListNode(0)
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next
    
    return dummy.next

Complexity

• Time: O(n), where n is the number of nodes in the linked list. We traverse the list twice: once to collect values and once to reconstruct it.
• Space: O(n), required to store the values in an array and to create the new linked list.

Recursive Approach

Intuition

Break down the problem into smaller subproblems by recursively swapping pairs and linking the results.

Steps

• Base case: If the list has fewer than two nodes, return the head as is.
• For the first two nodes, swap them and recursively call the function on the remaining list.
• Link the result of the recursive call to the second node (which becomes the new head after swapping).

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

def swapPairs(head):
    if not head or not head.next:
        return head
    
    first = head
    second = head.next
    
    first.next = swapPairs(second.next)
    second.next = first
    
    return second

Complexity

• Time: O(n), where n is the number of nodes in the linked list. Each node is visited once during the recursion.
• Space: O(n), due to the recursion stack. In the worst case, the recursion depth is n/2 for a list with n nodes.

Iterative Approach with Dummy Node

Intuition

Use a dummy node to simplify edge cases and iteratively swap pairs by adjusting pointers.

Steps

• Create a dummy node that points to the head of the list to handle the first pair uniformly.
• Use a pointer to track the previous node before the current pair.
• In each iteration, identify the two nodes to be swapped, adjust their pointers, and move the previous pointer forward.

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

def swapPairs(head):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    
    while prev.next and prev.next.next:
        first = prev.next
        second = prev.next.next
        
        prev.next = second
        first.next = second.next
        second.next = first
        
        prev = first
    
    return dummy.next

Complexity

• Time: O(n), where n is the number of nodes in the linked list. We iterate through the list once.
• Space: O(1), as we only use a constant amount of extra space for pointers.