Merge Two Linked Lists

Given two singly linked lists whose values are in non-decreasing order, merge them into one sorted list by repeatedly comparing the two current heads and appending the smaller node to a result chain. This is the same merge step as in merge sort. Time O(n + m) for lengths n and m; extra space O(1) if you only relink existing nodes (no new node allocation). A dummy head node avoids special-casing the first link.

C program (dummy head, in-place relink)

Both lists are built with insert_begin as in insert at beginning. List a: inserts 30, 20, 10 → 10 → 20 → 30. List b: 40, 25, 15 → 15 → 25 → 40. merge_sorted(a, b) returns the merged list 10 → 15 → 20 → 25 → 30 → 40. main prints both inputs, then the merged list, then free_list once on the merged head (the original pointers must not be freed again).

Equal keys: this code takes from a first when a->data == b->data (tie-break; either consistent rule is fine).
When one list is exhausted, tail->next is set to the remainder of the other—no need to walk it node by node.

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

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

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

struct Node *merge_sorted(struct Node *a, struct Node *b)
{
    struct Node dummy;
    struct Node *tail = &dummy;
    dummy.next = NULL;

    while (a != NULL && b != NULL) {
        if (a->data <= b->data) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = (a != NULL) ? a : b;
    return dummy.next;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void free_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

int main(void)
{
    struct Node *a = NULL;
    struct Node *b = NULL;

    a = insert_begin(a, 30);
    a = insert_begin(a, 20);
    a = insert_begin(a, 10);

    b = insert_begin(b, 40);
    b = insert_begin(b, 25);
    b = insert_begin(b, 15);

    printf("a: ");
    print_list(a);   /* 10 20 30 */
    printf("b: ");
    print_list(b);   /* 15 25 40 */

    struct Node *merged = merge_sorted(a, b);

    printf("merged: ");
    print_list(merged);   /* 10 15 20 25 30 40 */

    free_list(merged);
    return 0;
}

Program output

a: 10 20 30
b: 15 25 40
merged: 10 15 20 25 30 40

Overall program flow

Step	Operation	Pointers	Notes
1	Build `a` and `b` with `insert_begin`	`a`, `b` at list heads	`10→20→30` and `15→25→40`
2	Print `a` and `b`	Unchanged	Two lines of output
3	`merged = merge_sorted(a, b)`	Single chain from `dummy.next`	Nodes relinked; do not use `a`/`b` as separate lists anymore
4	`print_list(merged)`	—	Sorted merge output
5	`free_list(merged)`	All nodes freed	One traversal frees every node once

Pointer walk inside `merge_sorted` (first three attaches)

Illustrative addresses: a: 10 at 0x3000, 20 at 0x2000, 30 at 0x1000. b: 15 at 0x4000, 25 at 0x3500, 40 at 0x2500.

Step	`a` head	`b` head	Choice	New tail points to
1	`0x3000` (10)	`0x4000` (15)	`10 ≤ 15` → take from `a`	node `10`
2	`0x2000` (20)	`0x4000` (15)	`15 < 20` → take from `b`	node `15`
3	`0x2000` (20)	`0x3500` (25)	`20 ≤ 25` → take from `a`	node `20`

The loop continues until one of a or b is NULL; then tail->next is assigned the non-empty remainder in one step.

Memory layout (before merge, conceptual)

List	Head	Chain (values)
`a`	`0x3000`	`10 → 20 → 30 → ∅`
`b`	`0x4000`	`15 → 25 → 40 → ∅`

Visual representation

a:  10 ──→ 20 ──→ 30 ──→ ∅
b:  15 ──→ 25 ──→ 40 ──→ ∅
              merge_sorted
                ↓
merged:  10 ──→ 15 ──→ 20 ──→ 25 ──→ 30 ──→ 40 ──→ ∅

Detailed step-by-step: first iteration of the `while`

Initially a points to 10, b to 15, tail is the dummy’s node (stack), dummy.next is NULL.

Line	Code	Effect
1	`if (a->data <= b->data)`	`10 ≤ 15` → true: attach from `a`
2	`tail->next = a;`	`dummy.next` (via `tail`) now points to the `10` node
3	`a = a->next;`	`a` advances to the `20` node
4	`tail = tail->next;`	`tail` moves to the node containing `10`

Complexity summary

Operation	Time	Extra space
`merge_sorted`	`O(n + m)` — each pointer step consumes one node from `a` or `b`	`O(1)` — dummy on stack; no new list nodes
Building inputs with `insert_begin`	`O(n + m)` total	`O(n + m)` nodes allocated
`print_list` / `free_list`	linear in list length	`O(1)`

The key takeaway is that sorted input lets you merge by only looking at the two front nodes—like merging two sorted arrays with two indices, but pointers instead of indices. See also remove duplicates on a sorted list for another single-pass pattern on ordered chains.

If inputs are not sorted, sort each list first or collect values differently—merging as written assumes non-decreasing order. To merge by allocating new nodes instead of relinking, walk the same comparison logic and malloc each step (same time, more space).