Merge Two Sorted Lists - C Solution

1. Introduction

This post addresses a fundamental problem in linked list manipulation, known as "Merge Two Sorted Lists". The challenge lies in merging two sorted linked lists into a single sorted list by splicing together their nodes. This problem is a classic example of linked list traversal and merging techniques in C programming.

Problem

Given the heads of two sorted linked lists list1 and list2, the task is to merge these lists into one sorted list. The final merged list should be constructed by combining the nodes of the two given lists without creating new nodes.

2. Solution Steps

1. Initialize a dummy node to act as the starting point of the merged list.

2. Compare the current nodes of both lists, appending the smaller one to the merged list.

3. Advance the pointer in the list from which the smaller node was taken.

4. Continue the process until one of the lists is fully traversed.

5. Append the remaining part of the other list to the merged list.

6. Return the head of the merged list, which will be the next node of the dummy node.

3. Code Program

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

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// Function to merge two sorted lists
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;

    while (list1 && list2) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    tail->next = list1 ? list1 : list2;
    return dummy.next;
}

// Helper function to create a new ListNode
struct ListNode* newNode(int val) {
    struct ListNode* node = (struct ListNode*) malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Main function to demonstrate merging of two sorted lists
int main() {
    // Create first sorted list: 1 -> 2 -> 4
    struct ListNode* list1 = newNode(1);
    list1->next = newNode(2);
    list1->next->next = newNode(4);

    // Create second sorted list: 1 -> 3 -> 4
    struct ListNode* list2 = newNode(1);
    list2->next = newNode(3);
    list2->next->next = newNode(4);

    // Merge the two sorted lists
    struct ListNode* mergedList = mergeTwoLists(list1, list2);

    // Print and free the merged list
    printf("Merged List: ");
    while (mergedList != NULL) {
        printf("%d ", mergedList->val);
        struct ListNode* temp = mergedList;
        mergedList = mergedList->next;
        free(temp);
    }

    // No need to free list1 and list2 as their nodes are now part of mergedList
    return 0;
}

Output:

Merged List: 1 1 2 3 4 4

Explanation:

1. mergeTwoLists function iteratively compares nodes of both lists and builds the merged list.

2. A dummy node is used to simplify handling the head of the merged list.

3. The main function creates two example sorted lists, merges them, and prints the result.

4. Memory management is handled by freeing nodes of the merged list after printing.