Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

1. Need merged elements in a new list, not in the existing list.

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:

1. Iterative Method

2. 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 head of list 2, L3 pointing 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.

a.  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
* Author   : prodevelopertutorial.com
* Purpose  : Merge Two Sorted Lists
* 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* 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 iterative solution

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

Output 2: Using recursive solution

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

Let me know your thoughts in the comment section of the post below.