Merging Two Sorted Singly Linked Lists

Introduction

This document describes a method for merging two sorted singly linked lists into a single sorted singly linked list using C. It includes an explanation of the algorithm, a complete code implementation, and example usage.

Algorithm Explanation

The basic approach for merging two sorted singly linked lists into one sorted singly linked list is as follows:

1. Initialization: Create a dummy node as the starting point of the new list to simplify operations.
2. Merging Process: Compare the head nodes of both lists, select the smaller node as the next node of the new list, advance the pointer of the corresponding list, and repeat this process until one list becomes empty.
3. Handling Remaining Nodes: Directly attach the remaining nodes of the non-empty list to the end of the new list.
4. Returning the Result: Return the node following the dummy node as the head of the merged list.

In the best case, merging two sorted lists each of length N requires a minimum of (2N - 1) comparisons.

Complete Code

Below is the complete C implementation:

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

// Define linked list node structure
struct ListNode {
    int val;
    struct ListNode* next;
};

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

// Merge two sorted linked lists
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // Create a dummy node as starting point of new list
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;
    
    // Merge two linked lists
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    // Attach remaining nodes to end of new list
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }
    
    return dummy.next;
}

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

// Free linked list memory
void freeList(struct ListNode* head) {
    struct ListNode* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    // Create first sorted linked list: 1 -> 3 -> 5
    struct ListNode* l1 = createNode(1);
    l1->next = createNode(3);
    l1->next->next = createNode(5);
    
    // Create second sorted linked list: 2 -> 4 -> 6
    struct ListNode* l2 = createNode(2);
    l2->next = createNode(4);
    l2->next->next = createNode(6);
    
    // Merge linked lists
    struct ListNode* mergedList = mergeTwoLists(l1, l2);
    
    // Print merged linked list
    printf("Merged List: ");
    printList(mergedList);
    
    // Free linked list memory
    freeList(mergedList);
    
    return 0;
}

Usage Example

Input

Suppose we have two sorted linked lists:

• First list: 1 -> 3 -> 5
• Second list: 2 -> 4 -> 6

Output

The merged list is:

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

Code Explanation

1. Structure Definition:

   • struct ListNode defines the structure of a linked list node, containing an integer value and a pointer to the next node.

2. Node Creation:

   • The createNode function creates a new node.

3. Merge Function:

   • The mergeTwoLists function takes the head nodes of two sorted linked lists and returns the head node of the merged sorted list.
   • Uses a dummy node dummy as the starting point of the merged list to simplify operations.
   • Compares nodes from both lists one by one, linking the smaller node to the new list and advancing the corresponding list pointer.
   • Finally, directly attaches any remaining unprocessed list nodes to the end of the new list.

4. Print Function:

   • The printList function prints all node values in the list.

5. Memory Deallocation:

   • The freeList function frees the memory occupied by the linked list.

6. Main Function:

   • Creates two example sorted linked lists.
   • Calls mergeTwoLists to merge the lists and prints the result.
   • Frees the memory of the merged list.

Comparison Count Analysis

If all elements of one list are smaller than all elements of the other list, then only (N) comparisons are needed. In this case, all nodes of one list are directly merged into the result list, and then all remaining nodes of the other list are appended directly to the result list without any further comparisons.

1. Minimum Comparison Count (Special Case): In the extreme case where all nodes in list A are smaller than all nodes in list B, only N comparisons are needed. For example, if every node in list A is smaller than the first node in list B, we can fully merge list A into the result list after N comparisons and then append all nodes of list B to the result list. In this case, only N comparisons are required.

2. Worst Case (General Case): In the worst case, after each comparison, the smaller node from the two lists is selected and added to the result list before the next comparison. In this case, there are 2N nodes to process in total, and one node is added to the result list after each comparison, requiring (2N - 1) comparisons.

Summary

• Minimum Comparison Count: (N) comparisons (when all elements of one list are smaller than all elements of the other list).
• Worst Case Comparison Count: (2N - 1) comparisons (in the general case, where alternating comparisons and merges of all nodes from both lists are required).

Therefore, the minimum comparison count is indeed N. In the worst case, (2N - 1) comparisons are needed.