Pairwise swap adjacent nodes of a linked list

#include<stdio.h>

#include<stdlib.h>

// Data Structure to store a linked list node

struct Node

{

    int data;

    struct Node *next;

};

// Helper function to insert new node in the beginning of the linked list

void push(struct Node** headRef, int data)

{

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->next = *headRef;

    *headRef = newNode;

}

// Helper function to print the linked list

void printList(char *msg, struct Node *node)

{

    printf(“%s: “, msg);

    while (node) {

        printf(“%d -> “, node->data);

        node = node->next;

    }

    printf(“NULLn”);

}

// Function to pairwise swap adjacent nodes of a linked list

void rearrange(struct Node **head, struct Node *prev)

{

    // base case: if list is empty or contains just one node    

    if (*head == NULL || (*head)->next == NULL)

        return;

    struct Node *curr = *head;

    struct Node* temp = curr->next;

    curr->next = temp->next;

    temp->next = curr;

    if (prev == NULL)

        *head = temp;

    else

        prev->next = temp;

    prev = curr;

    rearrange(&(curr->next), prev);

}

// The wrapper function to call rearrange()

void _rearrange(struct Node **head)

{

    rearrange(head, NULL);

}

// main function

int main(void)

{

    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };

    unsigned n = sizeof(arr)/sizeof(arr[0]);

    struct Node *head = NULL;

    for (int i = n 1; i >= 0; i)

        push(&head, arr[i]);

    printList(“Before”, head);

    _rearrange(&head);

    printList(“After “, head);

    return 0;

}

Leave a Reply

Your email address will not be published. Required fields are marked *