填空答案

完整代码（原模板 + 填空）

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

// 链表节点结构
typedef struct Node {
    int value;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// 读取链表
Node* readList() {
    int value;
    Node* head = NULL;
    Node* tail = NULL;
    //尾插法
    while (1) {
        scanf("%d", &value);
        if (value == 0) break;   
        Node* newNode = createNode(value);
        if (head == NULL) {
            head = newNode;
        } else {
            tail->next = newNode;
        }
        tail = newNode;
    }
    
    return head;
}

// 合并两个有序链表（不去重）
Node* mergeLists(Node* list1, Node* list2) {
    Node* result = NULL;
    Node* tail = NULL;
    
    while (list1 != NULL && list2 != NULL) {
        Node* newNode;
        if (list1->value <= list2->value) {
            newNode = createNode(list1->value);
            list1 = list1->next;
        } else {
            newNode = createNode(list2->value);
            list2 = list2->next;
        }
        
        if (result == NULL) {
            result = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    
    // 处理剩余list1节点，修复tail空指针问题
    while (list1 != NULL) {
        Node* newNode = createNode(list1->value);
        if (result == NULL) {
            result = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
        list1 = list1->next;
    }
    
    // 处理剩余list2节点，修复tail空指针问题
    while (list2 != NULL) {
        Node* newNode = createNode(list2->value);
        if (result == NULL) {
            result = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
        list2 = list2->next;
    }
    
    return result;
}

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

int main() {
    // 读取两个链表
    Node* list1 = readList();
    Node* list2 = readList();
    
    // 判断两个链表是否都为空
    if (list1 == NULL && list2 == NULL) {
        printf("Empty\n");
        return 0;
    }
    
    // 合并链表
    Node* merged = mergeLists(list1, list2);
    
    // 输出合并后的链表
    Node* current = merged;
    while (current != NULL) {
        printf("%d", current->value);
        if (current->next != NULL) {
            printf(" ");
        }
        current = current->next;
    }
    printf("\n");
    
    // 释放内存
    freeList(list1);
    freeList(list2);
    freeList(merged);
    
    return 0;
}

思路讲解

整体在做什么

程序分三步：

1. readList()：把一行数字（以 0 结尾）读成一条链表，用尾插法保证顺序和输入一致；
2. mergeLists()：像拉拉链一样合并两条有序链表——每次比较两条链表当前的值，谁小取谁（相等取 list1），接到结果末尾，被取走的那条往后走一步；
3. 一条链先走完时，把另一条剩下的节点逐个接到结果后面。

逐个填空解释

空 1：(Node*)malloc(sizeof(Node))

createNode 要"造"一个新节点，节点在堆上申请内存。malloc(sizeof(Node)) 申请一块 Node 大小的空间，(Node*) 是把返回的空指针转成 Node 指针。申请后紧跟的两行把值和 next 初始化好。

空 2：head = newNode

第一个节点加入时链表还是空的（head == NULL），它自然就是表头。

空 3：tail->next = newNode

尾插法核心：链表不空时，把新节点接到当前最后一个节点（tail 指着它）的后面。注意两个分支结束后都有 tail = newNode，把尾巴更新成新节点——这就是"尾插法"能保持顺序的原因。

空 4：tail->next = newNode; tail = newNode;

合并时同理：结果链表不为空，新节点接到结果尾部，然后 tail 后移。两条语句缺一不可——漏了第一条节点接不上，漏了第二条下一个节点会覆盖而不是接续。

样例演算

输入：

1 3 4 0
1 2 4 0

list1 = 1→3→4，list2 = 1→2→4。合并过程：

易错点

• 空 3 只写 tail->next = newNode 一条就够，因为 tail = newNode 在 if/else 外面统一执行；但空 4 在 if/else 里面，两条语句都要写。
• malloc 的强制转换 (Node*) 在 C 里可以省略，但写上是好习惯。
• 不要改动模板的任何结构（包括 while (1)、循环内的判断顺序），填空题判分只认填空处的代码。
• 两个链表都空输出 Empty；输入行 0 0 和 0 等价（读到第一个 0 即停，0 不能作为结点值）。