How to Merge Two Sorted Linked Lists in C: Simple Guide

To merge two sorted linked lists in C, create a new list by comparing the head nodes of both lists and repeatedly attaching the smaller node to the new list. Use struct pointers to traverse and link nodes until all nodes from both lists are merged in sorted order.

Syntax

The function to merge two sorted linked lists typically takes two pointers to the head nodes of the lists and returns a pointer to the head of the merged sorted list.

• struct Node*: Pointer to a linked list node.
• mergeSortedLists(struct Node* l1, struct Node* l2): Function signature.
• The function compares nodes and links them in sorted order.

c

struct Node* mergeSortedLists(struct Node* l1, struct Node* l2);

Example

This example shows how to merge two sorted linked lists and print the merged list.

c

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

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

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Function to merge two sorted linked lists
struct Node* mergeSortedLists(struct Node* l1, struct Node* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    struct Node* result = NULL;

    if (l1->data <= l2->data) {
        result = l1;
        result->next = mergeSortedLists(l1->next, l2);
    } else {
        result = l2;
        result->next = mergeSortedLists(l1, l2->next);
    }
    return result;
}

// Function to print the linked list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

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

    // Create second sorted list: 2->4->6
    struct Node* l2 = newNode(2);
    l2->next = newNode(4);
    l2->next->next = newNode(6);

    struct Node* merged = mergeSortedLists(l1, l2);

    printf("Merged sorted list: ");
    printList(merged);

    return 0;
}

Output

Merged sorted list: 1 2 3 4 5 6 

Common Pitfalls

Common mistakes when merging sorted linked lists include:

• Not handling the case when one list is empty.
• Forgetting to update the next pointer correctly, causing loops or lost nodes.
• Using iterative approach without a dummy node can complicate linking nodes.
• Not freeing memory if dynamically allocated nodes are replaced or lost.

Always check for NULL pointers before accessing node data.

c

/* Wrong approach: Not checking for NULL before accessing data */
struct Node* mergeWrong(struct Node* l1, struct Node* l2) {
    struct Node* result = NULL;
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    if (l1->data <= l2->data) {
        result = l1;
        result->next = mergeWrong(l1->next, l2);
    } else {
        result = l2;
        result->next = mergeWrong(l1, l2->next);
    }
    return result;
}

/* Correct approach: Check for NULL first */
struct Node* mergeRight(struct Node* l1, struct Node* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    struct Node* result = NULL;
    if (l1->data <= l2->data) {
        result = l1;
        result->next = mergeRight(l1->next, l2);
    } else {
        result = l2;
        result->next = mergeRight(l1, l2->next);
    }
    return result;
}

Quick Reference

• Use recursion or iteration to merge nodes by comparing their data.
• Always check for NULL to avoid crashes.
• Return the head of the merged list for further use.
• Use helper functions to create and print lists for clarity.

Key Takeaways

Always check for NULL pointers before accessing linked list nodes.

Merge by comparing node values and linking the smaller node first.

Use recursion or iteration with a dummy node to simplify merging.

Handle empty lists as base cases to avoid errors.

Test merged list by printing to verify correct order.