Merge Two Sorted Linked Lists in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging two sorted linked lists

What is the printed state of the merged linked list after merging these two sorted lists?

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

DSA C

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

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

// After merging, print the list nodes in order separated by ' -> ' and ending with ' -> null'.

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

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

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

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

💡 Hint

Think about how the merge compares the current nodes of both lists and picks the smaller one first.

The merge function compares nodes from both lists and picks the smaller node to continue building the merged list. So the merged list is sorted and contains all nodes from both lists in order.

❓ Predict Output

intermediate

Output after merging lists with duplicates

Given two sorted linked lists:
List 1: 1 -> 2 -> 4 -> null
List 2: 1 -> 3 -> 4 -> null
What is the printed merged list?

DSA C

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

A 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null

B 1 -> 2 -> 3 -> 4 -> null

C 1 -> 3 -> 4 -> 1 -> 2 -> 4 -> null

D 2 -> 3 -> 4 -> 4 -> null

💡 Hint

Duplicates are allowed and merged in sorted order.

The merge function includes duplicates and keeps the order by always choosing the smaller or equal node first.

🔧 Debug

advanced

Identify the error in this merge function

What error will this merge function cause when merging two sorted linked lists?

DSA C

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

A Correctly merges the lists

B Infinite recursion causing stack overflow

C Segmentation fault (accessing NULL pointer)

D Compilation error due to missing return

💡 Hint

What happens if one list is empty (NULL)?

The function does not check if l1 or l2 is NULL before accessing l1->data or l2->data, causing a segmentation fault if either list is empty.

❓ Predict Output

advanced

Output of iterative merge of two sorted linked lists

What is the printed merged list after running this iterative merge function on:
List 1: 1 -> 4 -> 7 -> null
List 2: 2 -> 3 -> 6 -> null

DSA C

struct Node* mergeListsIterative(struct Node* l1, struct Node* l2) {
    struct Node dummy;
    struct Node* tail = &dummy;
    dummy.next = NULL;
    while (l1 && l2) {
        if (l1->data < l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

A 1 -> 2 -> 3 -> 4 -> 7 -> 6 -> null

B 1 -> 4 -> 7 -> 2 -> 3 -> 6 -> null

C 2 -> 3 -> 6 -> 1 -> 4 -> 7 -> null

D 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> null

💡 Hint

The iterative merge picks the smaller node each time and appends it to the result.

The function uses a dummy node and a tail pointer to build the merged list by choosing the smaller node from l1 or l2 until one list is empty, then appends the rest.

🧠 Conceptual

expert

Time complexity of merging two sorted linked lists

What is the time complexity of merging two sorted linked lists with lengths m and n?

A O(m + n)

B O(m * n)

C O(max(m, n)^2)

D O(log(m + n))

💡 Hint

Consider how many nodes are processed in total during the merge.

Each node from both lists is visited exactly once during the merge, so the total time is proportional to the sum of their lengths.