C语言合并两个有序链表

假设我们有两个有序链表，分别是 head1 和 head2，链表中的每个节点都有一个 val 值和一个 next 指针，表示该节点的值和下一个节点的地址。我们需要将这两个有序链表合并成一个新的有序链表。

具体实现如下：

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

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

struct ListNode* mergeTwoLists(struct ListNode* head1, struct ListNode* head2){
    // 创建一个新的链表 head，用于存储合并后的结果
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    head->next = NULL;

    // 创建一个指针 p，用于指向新链表的尾部
    struct ListNode *p = head;

    // 循环比较两个链表的节点，将小的节点加入到新链表中
    while (head1 != NULL && head2 != NULL) {
        if (head1->val < head2->val) {
            p->next = head1;
            head1 = head1->next;
        } else {
            p->next = head2;
            head2 = head2->next;
        }
        p = p->next;
    }

    // 将剩余的节点加入到新链表中
    if (head1 != NULL) {
        p->next = head1;
    }
    if (head2 != NULL) {
        p->next = head2;
    }

    // 返回新链表的头节点
    return head->next;
}

int main() {
    // 创建两个有序链表
    struct ListNode *head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *node1_1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *node1_2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    head1->val = 1;
    node1_1->val = 3;
    node1_2->val = 5;
    head1->next = node1_1;
    node1_1->next = node1_2;
    node1_2->next = NULL;

    struct ListNode *head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *node2_1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *node2_2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    head2->val = 2;
    node2_1->val = 4;
    node2_2->val = 6;
    head2->next = node2_1;
    node2_1->next = node2_2;
    node2_2->next = NULL;

    // 合并两个有序链表
    struct ListNode *head = mergeTwoLists(head1, head2);

    // 输出合并后的结果
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");

    return 0;
}

以上代码中，我们创建了两个有序链表，分别是 head1 和 head2。然后我们定义了一个新的链表 head，用于存储合并后的结果。接着我们定义了一个指针 p，用于指向新链表的尾部。

我们循环比较两个链表的节点，将小的节点加入到新链表中。如果其中一个链表已经遍历完了，我们将剩余的节点加入到新链表中。

最后，我们返回新链表的头节点，并输出合并后的结果。