Merge Two Sorted Linked Lists in DSA C - Build from Scratch

Merge Two Sorted Linked Lists

📖 Scenario: You are working on a simple contact list app. Each contact list is sorted by name. You want to merge two sorted contact lists into one sorted list.

🎯 Goal: Build a program that merges two sorted linked lists into one sorted linked list and prints the merged list.

📋 What You'll Learn

Create two sorted linked lists with exact values

Create a function to merge two sorted linked lists

Print the merged linked list in order

💡 Why This Matters

🌍 Real World

Merging sorted lists is common in contact apps, calendars, and any system that combines sorted data streams.

💼 Career

Understanding linked list merging is important for software engineering roles involving data structures and algorithm optimization.

1

Create two sorted linked lists

Create two sorted linked lists named list1 and list2 with these exact integer values: list1 contains 1, 3, 5 and list2 contains 2, 4, 6. Use the provided struct Node and create_node function.

DSA C

#include 
#include 

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

struct Node* create_node(int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

int main() {
    struct Node* list1 = NULL;
    struct Node* list2 = NULL;

    // Create list1 with nodes 1, 3, 5
    // Create list2 with nodes 2, 4, 6

    return 0;
}

Hint

Use create_node to create each node and link them using the next pointer.

2

Create a merge function

Create a function named merge_sorted_lists that takes two pointers to struct Node named list1 and list2 and returns a pointer to the merged sorted linked list. Use a dummy node to simplify merging.

DSA C

#include 
#include 

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

struct Node* create_node(int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

struct Node* merge_sorted_lists(struct Node* list1, struct Node* list2) {
    // Create a dummy node
    // Use pointers to merge nodes in sorted order
    // Return the merged list starting after dummy
    
    // Your code here
}

int main() {
    struct Node* list1 = create_node(1);
    list1->next = create_node(3);
    list1->next->next = create_node(5);

    struct Node* list2 = create_node(2);
    list2->next = create_node(4);
    list2->next->next = create_node(6);

    return 0;
}

Hint

Use a dummy node and a tail pointer to build the merged list. Compare list1->data and list2->data to decide which node to add next.

3

Merge the lists using the function

In main, call the merge_sorted_lists function with list1 and list2 as arguments. Store the result in a variable named merged_list.

DSA C

#include 
#include 

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

struct Node* create_node(int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

struct Node* merge_sorted_lists(struct Node* list1, struct Node* list2) {
    struct Node dummy;
    struct Node* tail = &dummy;
    dummy.next = NULL;

    while (list1 != NULL && list2 != NULL) {
        if (list1->data data) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    if (list1 != NULL) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }

    return dummy.next;
}

int main() {
    struct Node* list1 = create_node(1);
    list1->next = create_node(3);
    list1->next->next = create_node(5);

    struct Node* list2 = create_node(2);
    list2->next = create_node(4);
    list2->next->next = create_node(6);

    // Call merge_sorted_lists and store result in merged_list
    
    // Your code here

    return 0;
}

Hint

Call merge_sorted_lists(list1, list2) and assign the result to merged_list.

4

Print the merged linked list

Write a while loop to print the data of each node in merged_list separated by -> . End the output with null. Use printf inside the loop.

DSA C

#include 
#include 

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

struct Node* create_node(int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

struct Node* merge_sorted_lists(struct Node* list1, struct Node* list2) {
    struct Node dummy;
    struct Node* tail = &dummy;
    dummy.next = NULL;

    while (list1 != NULL && list2 != NULL) {
        if (list1->data data) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    if (list1 != NULL) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }

    return dummy.next;
}

int main() {
    struct Node* list1 = create_node(1);
    list1->next = create_node(3);
    list1->next->next = create_node(5);

    struct Node* list2 = create_node(2);
    list2->next = create_node(4);
    list2->next->next = create_node(6);

    struct Node* merged_list = merge_sorted_lists(list1, list2);

    // Print merged_list in format: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
    
    // Your code here

    return 0;
}

Hint

Use a while loop to go through each node in merged_list. Print the data followed by -> if there is a next node. After the loop, print null.