Swap Nodes in Pairs solution in C

Given a linked list, swap every two adjacent nodes and return its head.

Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

• Your algorithm should use only constant extra space.

• You may not modify the values in the list’s nodes, only nodes itself may be changed.

We can solve the above problem with 2 solutions.

1. Iterative

2. Recursive

According to the problem we need to solve it using constant space. If we use recursive solution, every time we make a recursive call we shall be occupying n/2 space in linear time. Hence we shall not solve it.

Let us study the steps involved in iterative solution:

Consider the initial list as shown below:

As we can see, node b is pointing to node c. If we make node b to point to node a, the address of node c will be lost.

Hence we shall save the address of node c in a temporary variable.

Then we swap 2 nodes, node a and node b, then we shall point the node a to node d. i.e temp->next.

Then before changing node c and node d, temp will be pointing to node e. then we shall change node c and node d.

Note:

The temp pointer should always point to the next node if the given pair.

In our iterative solution we take 4 pointers.

new_list_start_pointer : This will hold the starting point of new swapped list.

pointer_a:  This pointer will hold the address of first node of 2 nodes. For example, if we have 2 nodes “a” and “b”, it will hold the address of a.

pointer_b: This pointer will hold the address of second node of 2 nodes. For example, if we have 2 nodes “a” and “b”, it will hold the address of b.

temp_pointer: This will hold the address of next node of given pair.

/*
* File     : swap_nodes_pairwise.c
* Author   : prodevelopertutorial.com
* Purpose  : Swap nodes pairwise
* Copyright: @ prodevelopertutorial.com
*/

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

struct Node
{
    int data;
    struct Node* next;
};

// since we are 
void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}

struct Node* swap_node_pair_wise_iterative(struct Node *List_1)
{

    struct Node *new_list_start_pointer = NULL;
    struct Node *pointer_a = List_1; // now pointer a will point to 1st element in the pair

    //  This will hold the starting point of new swapped list. 
    //  As the starting point is the second node, we shall save that address
    new_list_start_pointer = pointer_a->next; 
    

    struct Node *pointer_b = NULL;
    struct Node *temp_pointer = NULL;
    while(1)
    {
        pointer_b = pointer_a->next; // now pointer b will point to 2nd element in the pair
        temp_pointer = pointer_b->next; // now it will hold the address of next node of given pair
        
        pointer_b->next = pointer_a; // make node b pointing to node a. Refer image 2.
    
            if(temp_pointer == NULL) // if we come at the end of the list break the loop. As pointer_a is the last node, assign it to null
            {
                pointer_a->next = NULL;
                break;
            }
            
            if(temp_pointer->next == NULL) // if we come at the end of the list break the loop. As pointer_a is the last node, assign it to null
            {
                pointer_a->next = temp_pointer;
                break;      
            }
    
        pointer_a->next = temp_pointer->next; // here node a will point to node d. Refer image 3.
        pointer_a = temp_pointer;
    
    }
return new_list_start_pointer;

}


int main()
{
    struct Node *list_1 = NULL; 

    struct Node *head_pointer_from_iterative_solution = NULL; 
    struct Node *head_pointer_from_recursive_solution = NULL; 


    insert_at_begenning(&list_1,8);
    insert_at_begenning(&list_1,7);
    insert_at_begenning(&list_1,6);
    insert_at_begenning(&list_1,5);
    insert_at_begenning(&list_1,4);
    insert_at_begenning(&list_1,3);
    insert_at_begenning(&list_1,2);
    insert_at_begenning(&list_1,1);

    printf("List 1 is\n");
    display_list(&list_1);

    


    head_pointer_from_iterative_solution = swap_node_pair_wise_iterative(list_1);
    
    printf("The result list using iterative method is\n");
    display_list(&head_pointer_from_iterative_solution);



    // head_pointer_from_recursive_solution = merge_two_sorted_lists_recursive(list_1, list_2);
    
    // printf("The result list using recursive method is\n");
    // display_list(&head_pointer_from_recursive_solution);

    return 0;
}

List 1 is
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
The result list using iterative method is
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7