Swap Nodes in Pairs

In this blog post, we will discuss the problem of swapping nodes in pairs in a linked list. We will explore the problem statement, the approach, and the code implementation in C++.

Problem Statement

Given a linked list, we need to swap every two adjacent nodes and return the modified linked list. If the number of nodes in the linked list is odd, the last node should remain as it is.

Approach

To solve this problem, we can use a recursive approach. We'll define a recursive function called swapPairs that takes the head of the linked list as its parameter. The function will perform the following steps:

1. Check the base case: If the current node or the next node is null, return the current node as there is nothing to swap.

2. Swap the current node and the next node by assigning the next node to a temporary variable nextNode. Update the next pointers of both nodes accordingly.

3. Recurse on the remaining linked list by calling swapPairs on the original next node's next.

Return the modified linked list by returning the nextNode.

Implementation

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* swapPairs(ListNode* head) {
        // Base case: If the current node or the next node is null, return the current node
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    // Swap the current node and the next node
    ListNode* nextNode = head->next;
    head->next = swapPairs(nextNode->next);
    nextNode->next = head;

    // Return the modified linked list
    return nextNode;
}

Time Complexity

The time complexity of this approach is O(N), where N is the number of nodes in the linked list. We visit each node exactly once.

Space Complexity

The space complexity is O(N) as well, considering the recursion stack. In the worst case, the depth of the recursion stack is equal to the number of nodes in the linked list.

Conclusion

By using a recursive approach, we can swap adjacent nodes in the given linked list efficiently. This algorithm provides a simple and elegant solution to the problem. Understanding the recursion and the pointer manipulations involved is key to grasping the concept behind this approach.