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.

Practice

1. What is the main goal when merging two sorted linked lists?

easy

A. To create a new sorted linked list containing all elements from both lists

B. To reverse both linked lists

C. To find the maximum element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the merge operation

   Merging two sorted linked lists means combining their elements into one list that remains sorted.

2. Step 2: Identify the goal

   The goal is to create a new sorted linked list that contains all elements from both input lists in order.

3. Final Answer:

   To create a new sorted linked list containing all elements from both lists -> Option A

4. Quick Check:

   Merge = combine sorted lists [OK]

Hint: Merging means combining sorted lists into one sorted list [OK]

Common Mistakes:

• Thinking merge reverses lists
• Confusing merge with finding max element
• Assuming merge removes duplicates

2. Which of the following is the correct way to declare a node structure for a singly linked list in C?

easy

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

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

C. struct Node { int data; struct Node next; };

D. struct Node { int data; struct Node* prev; };

Solution

1. Step 1: Check struct syntax for linked list node

   In C, a node contains data and a pointer to the next node. The pointer must be declared as 'struct Node* next;'.

2. Step 2: Identify correct declaration

   struct Node { int data; struct Node* next; }; correctly declares 'struct Node' with 'int data' and 'struct Node* next;'. struct Node { int data; Node* next; }; misses 'struct' keyword before Node*, struct Node { int data; struct Node next; }; incorrectly uses 'struct Node next;' (not a pointer), and struct Node { int data; struct Node* prev; }; uses 'prev' which is for doubly linked lists.

3. Final Answer:

   struct Node { int data; struct Node* next; }; -> Option A

4. Quick Check:

   Node struct needs pointer to next node [OK]

Hint: Node pointer must use 'struct Node*' in C [OK]

Common Mistakes:

• Omitting 'struct' keyword before Node*
• Using node instead of pointer for next
• Confusing singly linked list with doubly linked list

3. What will be the output linked list after merging these two sorted linked lists?

List1: 1 -> 3 -> 5 -> NULL
List2: 2 -> 4 -> 6 -> NULL

Assuming the merge function merges correctly.

medium

A. 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> NULL

B. 2 -> 4 -> 6 -> 1 -> 3 -> 5 -> NULL

C. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

D. 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> NULL

Solution

1. Step 1: Compare elements from both lists in order

   Start with heads: 1 (List1) and 2 (List2). 1 < 2, so 1 goes first. Then compare 3 and 2, 2 < 3, so 2 goes next. Continue this way to merge in sorted order.

2. Step 2: Build merged list step-by-step

   Merged list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL -> Option C

4. Quick Check:

   Merge keeps sorted order [OK]

Hint: Pick smaller node each step to merge sorted lists [OK]

Common Mistakes:

• Appending one list after the other without sorting
• Reversing the order accidentally
• Skipping nodes during merge

4. Consider this buggy merge function snippet in C:

struct Node* merge(struct Node* l1, struct Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->data < l2->data) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

What is the main issue if this function is called with two sorted lists?

medium

A. It reverses the merged list

B. It merges lists correctly without issues

C. It loses nodes when one list is empty

D. It causes infinite recursion when lists have equal elements

Solution

1. Step 1: Analyze base cases

   If one list is empty (!l1 or !l2), it correctly returns the other list.

2. Step 2: Analyze recursive case

   If l1->data < l2->data, it sets l1->next to the merge of the rest and returns l1. Otherwise, sets l2->next to merge(l1, l2->next) and returns l2. However, when l1->data == l2->data, the else branch is taken repeatedly without advancing l1, causing infinite recursion.

3. Final Answer:

   It causes infinite recursion when lists have equal elements -> Option D

4. Quick Check:

   Equal elements cause infinite recursion due to no advancement in l1 [OK]

Hint: Recursive merge must handle equal elements to avoid infinite recursion [OK]

Common Mistakes:

• Thinking equal elements cause infinite recursion
• Believing it loses nodes on empty lists
• Assuming it reverses the list

5. You have two sorted linked lists:
List1: 1 -> 4 -> 7 -> NULL
List2: 2 -> 4 -> 6 -> 8 -> NULL

Write the merged sorted linked list after merging them and removing duplicate values.

hard

A. 1 -> 4 -> 7 -> 2 -> 4 -> 6 -> 8 -> NULL

B. 1 -> 2 -> 4 -> 6 -> 7 -> 8 -> NULL

C. 1 -> 2 -> 4 -> 4 -> 6 -> 7 -> 8 -> NULL

D. 1 -> 2 -> 6 -> 7 -> 8 -> NULL

Solution

1. Step 1: Merge lists in sorted order

   Merge elements: 1, 2, 4, 4, 6, 7, 8.

2. Step 2: Remove duplicate values

   Remove one of the duplicate 4's to get: 1 -> 2 -> 4 -> 6 -> 7 -> 8 -> NULL.

3. Final Answer:

   1 -> 2 -> 4 -> 6 -> 7 -> 8 -> NULL -> Option B

4. Quick Check:

   Merge + remove duplicates = sorted unique list [OK]

Hint: Merge then skip duplicates for unique sorted list [OK]

Common Mistakes:

• Leaving duplicates in merged list
• Appending lists without sorting
• Removing unique elements by mistake