C言語で、2つのソート済み連結リストをマージする方法は何ですか。

2つのソート済み連結リストをマージするには、2つのポインタを使用してそれぞれの連結リストのノードの値を比較し、ノードを順番に接続します。

具体的には以下のとおりです。

1. リンク先となる新しいヘッドノードポインタ newHead を定義し、以降のノードの接続に使用するポインタを定義する
2. 二つのソートされた連結リストのヘッダポインタを p1、p2 と定義し、初期値を、それぞれリスト1と2のヘッダに設定します。
3. リンクリスト1とリンクリスト2をそれぞれp1とp2で辿りながら、p1とp2が指すノードの値を比較します。
4. いずれかのリストの最後までたどり着いたら、もう一方のリストの残りをそのまま newHead の後ろにつなげる。
5. マージされた順序付けられた連結リストの先頭ノードである newHead の次のノードを返す。

コード例:

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p = newHead;

    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;

    while (p1 && p2) {
        if (p1->val <= p2->val) {
            p->next = p1;
            p1 = p1->next;
        } else {
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next;
    }

    if (p1) {
        p->next = p1;
    }

    if (p2) {
        p->next = p2;
    }

    return newHead->next;
}

int main() {
    // 创建链表1: 1 -> 2 -> 4
    struct ListNode* l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    l1->val = 1;
    l1->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    l1->next->val = 2;
    l1->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    l1->next->next->val = 4;
    l1->next->next->next = NULL;

    // 创建链表2: 1 -> 3 -> 4
    struct ListNode* l2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    l2->val = 1;
    l2->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    l2->next->val = 3;
    l2->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    l2->next->next->val = 4;
    l2->next->next->next = NULL;

    // 合并两个有序链表
    struct ListNode* mergedList = mergeTwoLists(l1, l2);

    // 输出合并后的链表：1 -> 1 -> 2 -> 3 -> 4 -> 4
    while (mergedList) {
        printf("%d ", mergedList->val);
        mergedList = mergedList->next;
    }

    return 0;
}

1 1 2 3 4 4