链表合并问题

解题思路:

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

// 定义链表结构体

typedef struct node {

    int id;         // 学号

    int score;      // 成绩

    struct node *next;  // 指向下一个节点的指针

} Node;

// 插入节点到链表中

void insert(Node **head, int id, int score) {

    Node *new_node = (Node *)malloc(sizeof(Node));

    new_node->id = id;

    new_node->score = score;

    new_node->next = NULL;

    if (*head == NULL) {

        *head = new_node;

    } else {

        Node *cur = *head;

        Node *prev = NULL;

        while (cur != NULL && cur->id < id) {

            prev = cur;

            cur = cur->next;

        }

        if (prev == NULL) {

            new_node->next = *head;

            *head = new_node;

        } else {

            prev->next = new_node;

            new_node->next = cur;

        }

    }

}

// 合并两个链表

Node *merge(Node *a, Node *b) {

    Node *head = NULL;

    Node *cur = NULL;

    while (a != NULL && b != NULL) {

        if (a->id < b->id) {

            if (head == NULL) {

                head = a;

                cur = a;

            } else {

                cur->next = a;

                cur = cur->next;

            }

            a = a->next;

        } else {

            if (head == NULL) {

                head = b;

                cur = b;

            } else {

                cur->next = b;

                cur = cur->next;

            }

            b = b->next;

        }

    }

    if (a != NULL) {

        if (head == NULL) {

            head = a;

        } else {

            cur->next = a;

        }

    }

    if (b != NULL) {

        if (head == NULL) {

            head = b;

        } else {

            cur->next = b;

        }

    }

    return head;

}

// 输出链表

void print(Node *head) {

    while (head != NULL) {

        printf("%d %d\n", head->id, head->score);

        head = head->next;

    }

}

int main() {

    int n, m;

    scanf("%d %d", &n, &m);

    Node *a = NULL;

    Node *b = NULL;

    // 读入a链表的数据

    for (int i = 0; i < n; i++) {

        int id, score;

        scanf("%d %d", &id, &score);

        insert(&a, id, score);

    }

    // 读入b链表的数据

    for (int i = 0; i < m; i++) {

        int id, score;

        scanf("%d %d", &id, &score);

        insert(&b, id, score);

    }

    // 合并两个链表

    Node *c = merge(a, b);

    // 输出链表

    print(c);

    return 0;

}