Merge Two Sorted Linked Lists in DSA C

Mental Model

We combine two sorted lists by always picking the smaller front item from either list and linking it to the new list.

Analogy: Imagine merging two lines of people sorted by height into one line, always letting the shorter person step forward first.

List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null
Merged: null

Dry Run Walkthrough

Input: list1: 1->3->5, list2: 2->4->6

Goal: Create one sorted list containing all elements from both lists

Step 1: Compare heads: 1 (list1) vs 2 (list2), pick 1

Merged: 1 -> null
List1: 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null

Why: We start merged list with the smaller first element

Step 2: Compare heads: 3 (list1) vs 2 (list2), pick 2

Merged: 1 -> 2 -> null
List1: 3 -> 5 -> null
List2: 4 -> 6 -> null

Why: Next smallest element is 2 from list2

Step 3: Compare heads: 3 (list1) vs 4 (list2), pick 3

Merged: 1 -> 2 -> 3 -> null
List1: 5 -> null
List2: 4 -> 6 -> null

Why: Pick smaller element 3 from list1

Step 4: Compare heads: 5 (list1) vs 4 (list2), pick 4

Merged: 1 -> 2 -> 3 -> 4 -> null
List1: 5 -> null
List2: 6 -> null

Why: Pick smaller element 4 from list2

Step 5: Compare heads: 5 (list1) vs 6 (list2), pick 5

Merged: 1 -> 2 -> 3 -> 4 -> 5 -> null
List1: null
List2: 6 -> null

Why: Pick smaller element 5 from list1

Step 6: List1 empty, append remaining list2 nodes

Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
List1: null
List2: null

Why: No more elements in list1, add rest of list2

Result:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for linked list
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// Create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

// Merge two sorted linked lists
Node* mergeTwoLists(Node* l1, Node* l2) {
    // Dummy node to start merged list
    Node dummy;
    Node* tail = &dummy;
    dummy.next = NULL;

    // While both lists have nodes
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            tail->next = l1; // link smaller or equal node
            l1 = l1->next;   // advance l1
        } else {
            tail->next = l2; // link smaller node
            l2 = l2->next;   // advance l2
        }
        tail = tail->next;    // move tail forward
    }

    // Attach remaining nodes
    if (l1 != NULL) tail->next = l1;
    else tail->next = l2;

    return dummy.next;
}

// Print linked list
void printList(Node* head) {
    while (head != NULL) {
        printf("%d", head->val);
        if (head->next != NULL) printf(" -> ");
        head = head->next;
    }
    printf(" -> null\n");
}

int main() {
    // Create list1: 1->3->5
    Node* l1 = newNode(1);
    l1->next = newNode(3);
    l1->next->next = newNode(5);

    // Create list2: 2->4->6
    Node* l2 = newNode(2);
    l2->next = newNode(4);
    l2->next->next = newNode(6);

    Node* merged = mergeTwoLists(l1, l2);
    printList(merged);
    return 0;
}

while (l1 != NULL && l2 != NULL) {

loop while both lists have nodes to compare

if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; }

pick smaller or equal node and advance that list

tail = tail->next;

move tail pointer forward to last node in merged list

if (l1 != NULL) tail->next = l1; else tail->next = l2;

append remaining nodes from non-empty list

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n + m) because we visit each node from both lists exactly once

Space: O(1) because we rearrange pointers without extra storage

vs Alternative: Compared to creating a new list and copying values, this approach saves space and time by reusing nodes

Edge Cases

One or both lists empty

Returns the non-empty list or NULL if both empty

DSA C

if (l1 != NULL) tail->next = l1; else tail->next = l2;

Lists with duplicate values

Duplicates are merged in sorted order without loss

DSA C

if (l1->val <= l2->val) { ... } else { ... }

Lists of different lengths

Remaining nodes of longer list appended after shorter list ends

DSA C

if (l1 != NULL) tail->next = l1; else tail->next = l2;

When to Use This Pattern

When you see two sorted lists and need one sorted list, use the merge pattern by picking smaller heads repeatedly.

Common Mistakes

Mistake: Not advancing the tail pointer after linking a node
Fix: Always move tail = tail->next after linking a node to keep track of the merged list end

Mistake: Forgetting to attach remaining nodes after one list ends
Fix: After the loop, attach the leftover nodes from the non-empty list

Summary

It merges two sorted linked lists into one sorted linked list by choosing nodes one by one.

Use it when you have two sorted lists and want a single sorted list combining both.

The key is always to pick the smaller front node and link it, then move forward.

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