Swap Nodes in Pairs - C++ Solution

1. Introduction

In this blog post, we'll explore a problem involving the manipulation of linked list nodes: swapping every two adjacent nodes in a linked list. This problem demonstrates an interesting use case of pointers in linked list operations.

Problem

Given a linked list, the task is to swap every two adjacent nodes and return the modified list's head. The values of the nodes should not be changed; only the nodes themselves may be rearranged.

2. Solution Steps

1. Create a dummy node to simplify edge cases, especially when swapping involves the head of the list.

2. Use three pointers: prev, current, and next, to keep track of the nodes being swapped.

3. Iterate through the list and swap pairs of nodes by changing their next pointers.

4. Return the head of the modified list, which is the next node of the dummy node.

3. Code Program

#include <iostream>
using namespace std;

// Define the ListNode structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to swap nodes in pairs
ListNode* swapPairs(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode *prev = &dummy;

    while (prev->next && prev->next->next) {
        ListNode *current = prev->next;
        ListNode *next = current->next;

        // Swap the nodes
        prev->next = next;
        current->next = next->next;
        next->next = current;

        // Move to the next pair
        prev = current;
    }

    return dummy.next;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    head = swapPairs(head);
    printLinkedList(head); // Expected output: 2 -> 1 -> 4 -> 3 -> nullptr
    return 0;
}

Output:

2 -> 1 -> 4 -> 3 -> nullptr

Explanation:

The swapPairs function swaps every two adjacent nodes in the linked list. 

It uses a dummy node to simplify the handling of the head of the list and employs three pointers (prev, current, and next) to manage the swapping process. 

The nodes are swapped by adjusting their next pointers. 

This approach efficiently swaps pairs of nodes in the list without altering the node values, as demonstrated in the output for the given example.