C语言合并两个带头节点升序排列链表

下面我将为你详细讲解“C语言合并两个带头节点升序排列链表”的完整攻略。

问题描述

假设有两个带头节点的升序排列链表，现在需要将它们合并成一个新的升序排列链表。

解决方案

1. 定义一个新的链表来存储合并后的结果，定义三个指针分别指向两个输入链表的头节点和新链表的尾节点。

2. 循环比较两个链表的当前节点，将较小的节点接入新链表的尾部，并将新链表的尾节点指向新加入的节点。

3. 如果一个链表为空，直接将另一个链表的剩余节点加入新链表的尾部即可。

4. 最后返回新链表的头节点即为合并后的结果。

下面是基于上述方案的代码实现：

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

typedef struct node {
    int value;
    struct node *next;
} Node;

/**
 * 合并两个带头节点升序排列链表
 * @param h1 第一个链表的头节点
 * @param h2 第二个链表的头节点
 * @return 合并后的升序排列链表的头节点
 */
Node *merge_sorted_lists(Node *h1, Node *h2) {
    Node *head = (Node *) malloc(sizeof(Node)); // 新链表的头节点
    Node *tail = head; // 新链表的尾节点，初始指向头节点
    Node *p1 = h1->next; // 第一个链表的当前节点
    Node *p2 = h2->next; // 第二个链表的当前节点

    // 循环比较两个链表的当前节点
    while (p1 != NULL && p2 != NULL) {
        if (p1->value < p2->value) {
            // 将较小的节点接入新链表的尾部
            tail->next = p1;
            tail = tail->next;
            p1 = p1->next;
        } else {
            tail->next = p2;
            tail = tail->next;
            p2 = p2->next;
        }
    }

    // 如果一个链表为空，直接将另一个链表的剩余节点加入新链表的尾部
    if (p1 != NULL) {
        tail->next = p1;
    }

    if (p2 != NULL) {
        tail->next = p2;
    }

    // 返回新链表的头节点即为合并后的结果
    return head;
}

int main() {
    // 示例1
    Node *h1 = (Node *) malloc(sizeof(Node)); // 第一个链表的头节点
    h1->next = NULL;
    Node *p1 = NULL; // 第一个链表的尾节点
    for (int i = 1; i <= 3; i++) {
        Node *node = (Node *) malloc(sizeof(Node));
        node->value = i * 2 - 1;
        node->next = NULL;
        if (p1 == NULL) {
            h1->next = node;
        } else {
            p1->next = node;
        }
        p1 = node;
    }

    Node *h2 = (Node *) malloc(sizeof(Node)); // 第二个链表的头节点
    h2->next = NULL;
    Node *p2 = NULL; // 第二个链表的尾节点
    for (int i = 1; i <= 4; i++) {
        Node *node = (Node *) malloc(sizeof(Node));
        node->value = i * 2;
        node->next = NULL;
        if (p2 == NULL) {
            h2->next = node;
        } else {
            p2->next = node;
        }
        p2 = node;
    }

    Node *head = merge_sorted_lists(h1, h2);
    Node *p = head->next;
    while (p != NULL) {
        printf("%d ", p->value);
        p = p->next;
    }
    printf("\n");

    // 示例2
    Node *h3 = (Node *) malloc(sizeof(Node)); // 第三个链表的头节点
    h3->next = NULL;
    Node *q1 = NULL; // 第三个链表的尾节点
    for (int i = 1; i <= 3; i++) {
        Node *node = (Node *) malloc(sizeof(Node));
        node->value = i * 2;
        node->next = NULL;
        if (q1 == NULL) {
            h3->next = node;
        } else {
            q1->next = node;
        }
        q1 = node;
    }

    Node *h4 = (Node *) malloc(sizeof(Node)); // 第四个链表的头节点
    h4->next = NULL;
    Node *q2 = NULL; // 第四个链表的尾节点
    for (int i = 1; i <= 3; i++) {
        Node *node = (Node *) malloc(sizeof(Node));
        node->value = i * 2 - 1;
        node->next = NULL;
        if (q2 == NULL) {
            h4->next = node;
        } else {
            q2->next = node;
        }
        q2 = node;
    }

    Node *head2 = merge_sorted_lists(h3, h4);

    Node *q = head2->next;
    while (q != NULL) {
        printf("%d ", q->value);
        q = q->next;
    }

    return 0;
}

示例说明

这里提供两个示例：

1. 示例1中存在两个输入链表，分别为{1,3,5}和{2,4,6,8}，合并后的升序排列链表为{1,2,3,4,5,6,8}。

2. 示例2中存在两个输入链表，分别为{2,4,6}和{1,3,5}，合并后的升序排列链表为{1,2,3,4,5,6}。