Swap Nodes in Pairs - C Solution

1. Introduction

This blog post addresses a common but intriguing problem in linked list manipulation using C programming: swapping nodes in pairs in a singly linked list. This challenge tests one's understanding of linked list operations, particularly pointer manipulation, without altering the node values.

Problem

Given a singly linked list, the task is to swap every two adjacent nodes and return the head of the modified list. The values within the nodes must not be changed; instead, the nodes themselves should be rearranged. This problem requires careful pointer operations to ensure the correct order of nodes.

2. Solution Steps

1. Use a dummy head to simplify edge cases.

2. Iterate through the list in pairs.

3. For each pair, swap the nodes by changing the pointers.

4. Move to the next pair and repeat until the end of the list.

5. Return the new head of the list (next node of the dummy head).

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// Function to swap nodes in pairs
struct ListNode* swapPairs(struct ListNode* head) {
    struct ListNode dummy; // Dummy head node
    dummy.next = head;
    struct ListNode *prev = &dummy, *current = head;

    while (current && current->next) {
        // Nodes to be swapped
        struct ListNode *first = current;
        struct ListNode *second = current->next;

        // Swapping
        prev->next = second;
        first->next = second->next;
        second->next = first;

        // Move to the next pair
        prev = first;
        current = first->next;
    }

    return dummy.next; // Return new head
}

// Utility function to create a new node
struct ListNode* newNode(int val) {
    struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Main function to demonstrate swapPairs function
int main() {
    // Create a sample list: 1->2->3->4
    struct ListNode* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);

    head = swapPairs(head); // Swap nodes in pairs

    // Print the modified list
    printf("Output: ");
    while (head != NULL) {
        printf("%d ", head->val);
        struct ListNode* temp = head;
        head = head->next;
        free(temp); // Free the node after printing
    }
    printf("\n");

    return 0;
}

Output:

2 1 4 3

Explanation:

The program swaps adjacent nodes in pairs in the given linked list. It uses a dummy head node to handle edge cases easily. 

In each iteration, two nodes are swapped by changing the pointers, not the node values. After swapping, the program moves to the next pair. 

In the example list 1->2->3->4, nodes are swapped in pairs to form the new list 2->1->4->3. 

This approach efficiently swaps nodes in pairs, demonstrating a clear understanding of pointer manipulation in linked lists.