Question 24

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve it using recursion.

Approach: Recursion

1. Base Case: If the list is empty or has only one node, return the head as no swapping is needed.
2. Recursive Step: Recursively solve the problem for the remaining nodes (i.e., after the first pair), then swap the first two nodes.
3. Return New Head: The new head of the list after the swap will be the second node in the first pair.

This recursive approach ensures that each pair is swapped as we progress through the list.

Complexity

• Time Complexity: ( O(n) ), where ( n ) is the number of nodes in the list. We traverse each node exactly once.
• Space Complexity: ( O(n) ), due to the recursion stack (worst case for a list of length ( n )).

Java Code Implementation

public class Solution {
    public ListNode swapPairs(ListNode head) {
        // Base case: If the list is empty or has only one node, return head
        if (head == null || head.next == null) {
            return head;
        }

        // Nodes to be swapped
        ListNode first = head;
        ListNode second = head.next;

        // Recursive call to swap the rest of the list
        first.next = swapPairs(second.next);

        // Perform the swap
        second.next = first;

        // Return the new head node, which is 'second'
        return second;
    }
}