Problem Explanation:
Given a linked list, swap every two adjacent nodes and return its head.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
We can solve the above problem with 2 solutions.
- Iterative
- 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 the 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, the 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.
Solution in C
In our iterative solution, we take 4 pointers.
new_list_start_pointer: This will hold the starting point of the new swapped list.
pointer_a: This pointer will hold the address of the 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 the 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 the next node of the given pair.
/* * File : swap_nodes_pairwise.c * Purpose : Swap nodes pairwise */ #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; }
Output:
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