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.