The two separate list, merge them to create a new list.
Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
The solution as expected is very simple.
In this tutorial we shall look at 2 different solutions:
- Iterative Method
- Recursion Method
For both the solution the concept will remain the same as explained below:
Step 1: Take 3 head pointers, L1 pointing head of list 1, L2 pointing the head of list 2, L3 pointing the head of list 3.
Step 2: Compare the data present in the pointer pointed by L1 to the data present in the pointer pointed by L2.
- If it is less, add to the new list L3, increment L1 pointer by 1 step.
b. Else, add the data pointed by L2 to L3 then move the L2 pointer by 1 step.
Step 3: Similarly, continue the step 2 till all the nodes from both the list are empty.
Visualization of the solution:
In Recursive solution, as you expect, we call the same function again to make us the decision.
The solution in C:
/* * File : merge_two_sorted_lists.c * Purpose : Merge Two Sorted Lists */ #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* merge_two_sorted_lists_iterative(struct Node *List_1, struct Node *List_2 ) { struct Node *new_list_head; // we initialize head for the new list and will use it to return back as a head pointer to new list struct Node *new_list_tail; // we initialize tail pointer to new list, we use this pointer to add new elements /* * If you observe carefully, we are just taking the pointer reference without allocating memory. * This is because, we have already allocated memory for List_1 and List_2, we modify address directly in the source lists. */ //testing, if any one of the list are empty we shall return the other list. if(!List_1) return List_2; if(!List_2) return List_1; // check if the list_1 is having the least value or list_2. And update the head and tail pointers appropriately. if(List_1->data < List_2->data) { new_list_head=new_list_tail=List_1; List_1=List_1->next; } else { new_list_head=new_list_tail=List_2; List_2=List_2->next; } //Till both of the list has a value, repeat. This is to handle uneven lists. while(List_1 && List_2) { // check for the next smallest value and update accordingly. if(List_1->data < List_2->data) { new_list_tail->next=List_1; new_list_tail = List_1; List_1=List_1->next; } else { new_list_tail->next=List_2; new_list_tail = List_2; List_2=List_2->next; } } // If one of two lists are having extra elements, we just link the tail pointer. // Note that we link them directly without comparing, because the list nodes are already sorted. if(List_1) new_list_tail->next=List_1; else new_list_tail->next=List_2; return new_list_head; } struct Node* merge_two_sorted_lists_recursive(struct Node *List_1, struct Node *List_2 ) { struct Node *new_list_head; // we initialize head for the new list and will use it to return back as a head pointer to new list if (List_1 == NULL) { return List_2; } if (List_2 == NULL) { return List_1; } if (List_1 -> data < List_2 -> data) { new_list_head = List_1; new_list_head -> next = merge_two_sorted_lists_recursive(List_1 -> next, List_2); } else { new_list_head = List_2; new_list_head -> next = merge_two_sorted_lists_recursive(List_1, List_2 -> next); } return new_list_head; } int main() { struct Node *list_1 = NULL; struct Node *list_2 = NULL; struct Node *head_pointer_from_iterative_solution = NULL; struct Node *head_pointer_from_recursive_solution = NULL; insert_at_begenning(&list_1,7); insert_at_begenning(&list_1,5); insert_at_begenning(&list_1,3); insert_at_begenning(&list_1,1); insert_at_begenning(&list_2,8); insert_at_begenning(&list_2,6); insert_at_begenning(&list_2,4); insert_at_begenning(&list_2,2); printf("List 1 is\n"); display_list(&list_1); printf("List 2 is\n"); display_list(&list_2); // head_pointer_from_iterative_solution = merge_two_sorted_lists_iterative(list_1, list_2); // 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: Using the iterative solution
List 1 is 1 -> 3 -> 5 -> 7 List 2 is 2 -> 4 -> 6 -> 8 The result list using the iterative method is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
Output 2: Using the recursive solution
List 1 is 1 -> 3 -> 5 -> 7 List 2 is 2 -> 4 -> 6 -> 8 The result list using the recursive method is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
Let me know your thoughts in the comment section of the post below.
No Responses