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

// 定义单链表的节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 定义单链表结构体
typedef struct SortedSinglyList {
    Node *head;
} SortedSinglyList;

// 函数声明
Node* createNode(int data);
void insertNode(SortedSinglyList *list, int data);
void mergeLists(SortedSinglyList *listA, SortedSinglyList *listB, SortedSinglyList *listC);
void printList(SortedSinglyList *list);
void freeList(SortedSinglyList *list);

// 创建新节点
Node* createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        exit(1); // 分配内存失败，退出程序
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 向链表中插入节点
void insertNode(SortedSinglyList *list, int data) {
    Node *newNode = createNode(data);
    if (list->head == NULL || data < list->head->data) {
        // 插入到头部
        newNode->next = list->head;
        list->head = newNode;
    } else {
        Node *current = list->head;
        while (current->next != NULL && current->next->data < data) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

// 打印链表
void printList(SortedSinglyList *list) {
    Node *current = list->head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 释放链表
void freeList(SortedSinglyList *list) {
    Node *current = list->head;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
    list->head = NULL;
}

// 合并两个有序单链表
void mergeLists(SortedSinglyList *listA, SortedSinglyList *listB, SortedSinglyList *listC) {
    Node *pa = listA->head->next;
    Node *pb = listB->head->next;
    Node *pc = listC->head;

    // 两表均从第一个元素开始依次扫描、比较
    while (pa != NULL && pb != NULL) {
        if (pa->data < pb->data) {
            insertNode(listC, pa->data);
            pa = pa->next;
        } else {
            insertNode(listC, pb->data);
            pb = pb->next;
        }
    }

    // 若剩余的是listA表，将表中剩余元素全部插入到listC表中
    while (pa != NULL) {
        insertNode(listC, pa->data);
        pa = pa->next;
    }

    // 若剩余的是listB表，将表中剩余元素全部插入到listC表中
    while (pb != NULL) {
        insertNode(listC, pb->data);
        pb = pb->next;
    }
}

// 主函数
int main() {
    // 创建有序单链表listA和listB
    SortedSinglyList listA, listB, listC;
    listA.head = createNode(0); // 头节点，不存放数据
    listB.head = createNode(0); // 头节点，不存放数据
    listC.head = createNode(0); // 头节点，不存放数据

    insertNode(&listA, 12);
    insertNode(&listA, 36);
    insertNode(&listA, 89);
    insertNode(&listA, 100);

    insertNode(&listB, 22);
    insertNode(&listB, 43);
    insertNode(&listB, 91);
    insertNode(&listB, 112);
    insertNode(&listB, 120);

    // 打印原始链表
    printf("List A: ");
    printList(&listA);
    printf("List B: ");
    printList(&listB);

    // 合并链表
    mergeLists(&listA, &listB, &listC);

    // 打印合并后的链表
    printf("Merged List C: ");
    printList(&listC);

    // 释放链表内存
    freeList(&listA);
    freeList(&listB);
    freeList(&listC);

    return 0;
}
