Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:

Input: list1 = [], list2 = []
Output: []
Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

Answer & Explaination

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

// Function to merge two sorted linked lists.
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // Create a dummy node to act as the start of the new list.
    struct ListNode dummy; //創立單一虛擬節點為新的鏈起點
    struct ListNode* tail = &dummy;
    dummy.next = NULL;

    // Traverse both lists and append the smaller value to the merged list.
    while (list1 != NULL && list2 != NULL) {
        if (list1->val <= list2->val) { //list1值<=list2
            tail->next = list1;//新的鏈的next指向list1
            list1 = list1->next;//移動list1到下一個
        } else { //list2值<=list1
            tail->next = list2;//新的鏈的next指向list2
            list2 = list2->next;//移動list2到下一個
        }
        tail = tail->next;//更新tail到下一個
    }

    // Append any remaining nodes from either list1 or list2.
    //處理任一個鏈的剩餘節點(當有任一方已為NULL時)
    if (list1 != NULL) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }

    return dummy.next;//回傳合併後串列的head node
    //因為dummy只是虛擬節點，所以要從下個node開始才是真正節點
}

Testing

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

// Definition for singly-linked list.
struct ListNode { //定義單個鏈的結構
    int val;
    struct ListNode *next;
};

// Function to merge two sorted linked lists.
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // Create a dummy node to act as the start of the new list.
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;

    // Traverse both lists and append the smaller value to the merged list.
    while (list1 != NULL && list2 != NULL) {
        if (list1->val <= list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    // Append any remaining nodes from either list1 or list2.
    if (list1 != NULL) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }

    return dummy.next;
}

// Helper function to create a new ListNode.
//用於創建節點
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// Helper function to print a linked list.
//用於印出節點
void printList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d -> ", current->val);
        current = current->next;
    }
    printf("NULL\n");
}

// Helper function to create a list from an array of values.
//從陣列創建鏈
struct ListNode* createList(int* arr, int size) {
    if (size == 0) return NULL;

    struct ListNode* head = createNode(arr[0]);
    struct ListNode* current = head;

    for (int i = 1; i < size; i++) { //不斷把陣列值帶入
        current->next = createNode(arr[i]);
        current = current->next;
    }

    return head;
}

// Test function
//測試函數
void testMergeTwoLists() {
    //設立兩個array
    int arr1[] = {1, 2, 4};
    int arr2[] = {1, 3, 4};
    //創立兩個list
    struct ListNode* list1 = createList(arr1, 3);
    struct ListNode* list2 = createList(arr2, 3);

    printf("List 1: \n");
    printList(list1);

    printf("List 2: \n");
    printList(list2);

    struct ListNode* mergedList = mergeTwoLists(list1, list2);//合併兩個陣列

    printf("Merged List: \n");
    printList(mergedList);
}

int main() {
    testMergeTwoLists();
    return 0;
}