用C语言实现两个链表按大小顺序合并

下面是一个示例代码，假设链表节点的结构体为Node，有两个链表head1和head2，将它们合并并按大小顺序排列：

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* merge(Node *head1, Node *head2) {
    Node *newHead = NULL;  // 合并后的新链表头节点
    Node *tail = NULL;  // 新链表的尾节点
    Node *p1 = head1;
    Node *p2 = head2;

    // 遍历两个链表，比较节点大小并将较小的节点插入到新链表中
    while (p1 != NULL && p2 != NULL) {
        Node *temp = NULL;
        if (p1->data < p2->data) {
            temp = p1;
            p1 = p1->next;
        } else {
            temp = p2;
            p2 = p2->next;
        }
        if (newHead == NULL) {
            newHead = temp;
            tail = temp;
        } else {
            tail->next = temp;
            tail = temp;
        }
    }

    // 将剩余的节点直接插入到新链表的尾部
    if (p1 != NULL) {
        tail->next = p1;
    } else {
        tail->next = p2;
    }

    return newHead;
}

int main() {
    Node *head1 = NULL;
    Node *head2 = NULL;

    // 构造两个有序链表
    for (int i = 1; i <= 5; i++) {
        Node *node = (Node*)malloc(sizeof(Node));
        node->data = i;
        node->next = NULL;
        if (head1 == NULL) {
            head1 = node;
        } else {
            Node *p = head1;
            while (p->next != NULL) {
                p = p->next;
            }
            p->next = node;
        }
    }

    for (int i = 3; i <= 8; i++) {
        Node *node = (Node*)malloc(sizeof(Node));
        node->data = i;
        node->next = NULL;
        if (head2 == NULL) {
            head2 = node;
        } else {
            Node *p = head2;
            while (p->next != NULL) {
                p = p->next;
            }
            p->next = node;
        }
    }

    // 输出原链表
    printf("head1: ");
    Node *p = head1;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    printf("head2: ");
    p = head2;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    // 合并链表并输出结果
    Node *newHead = merge(head1, head2);
    printf("merged: ");
    p = newHead;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    // 释放链表节点的内存
    p = head1;
    while (p != NULL) {
        Node *temp = p;
        p = p->next;
        free(temp);
    }

    p = head2;
    while (p != NULL) {
        Node *temp = p;
        p = p->next;
        free(temp);
    }

    p = newHead;
    while (p != NULL) {
        Node *temp = p;
        p = p->next;
        free(temp);
    }

    return 0;
}

输出结果如下：

head1: 1 2 3 4 5 
head2: 3 4 5 6 7 8 
merged: 1 2 3 3 4 4 5 5 6 7 8