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}。

阅读剩余 70%

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言合并两个带头节点升序排列链表 - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • iOS开发之App主题切换解决方案完整版(Swift版)

    下面我来详细介绍一下“iOS开发之App主题切换解决方案完整版(Swift版)”的完整攻略。 1. 简介 本文主要介绍在iOS开发中如何实现App主题切换功能的完整方案,包括主题配置、主题切换实现、持久化存储等方面,以及一些实际应用中的示例说明。 2. 主题配置和资源文件准备 2.1 主题配置 首先需要在项目中创建一个主题配置文件,用于存储各种主题需要用到的…

    other 2023年6月27日
    00
  • 关于python:cv2.merge((r g b))如何工作?

    以下是关于“关于python:cv2.merge((rgb))如何工作?”的完整攻略,包括cv2.merge()函数的用法和工作原理,以及两个示例说明。 cv2.merge()函数 在Python中,cv2.merge()函数用于将多个单通道图像合并为一个多通道图像。它的语法如下: cv2.merge(mv[, dst]) 在上面的语法中,mv是一个包含单通…

    other 2023年5月7日
    00
  • vue监听scroll的坑的解决方法

    标题:Vue监听scroll的坑的解决方法 问题背景 在Vue的开发中,经常需要监听scroll事件以实现一些滚动相关的交互效果。但是,在使用Vue绑定scroll事件时,会出现一些坑。 问题描述 在Vue中通过v-on指令绑定scroll事件之后,发现绑定的函数并没有被触发,示例代码如下: <template> <div class=&q…

    other 2023年6月27日
    00
  • 基于Python实现2种反转链表方法代码实例

    当我们需要对链表进行反转的时候,在Python中有很多种实现方式。本文将详细阐述两种反转链表的实现方法及其代码实例。 方法一:反转链表法 反转链表是最基础的一种方法,其实现思路很简单,就是对链表中的每个节点按照它们的next指针进行反转。首先我们定义一个新的链表头节点,然后遍历原始链表,每遍历到一个节点就将其作为头节点的下一节点,同时将其从原链表中删除。这样…

    other 2023年6月27日
    00
  • HTML5中通过li-canvas轻松实现单图、多图、圆角图绘制,单行文字、多行文字等

    HTML5中通过<canvas>标签实现绘图功能,<li>则可以用来结合canvas实现一些更加丰富的效果。下面,我将详细讲解如何通过li-canvas轻松实现单图、多图、圆角图绘制、单行文字、多行文字等的完整攻略。 准备工作 在开始使用li-canvas之前,需要准备以下工作: 引入li-canvas库文件:在HTML的标签中引用l…

    other 2023年6月27日
    00
  • C语言例题讲解指针与数组

    C语言例题讲解指针与数组 本文将通过两个实例,详细讲解指针与数组在C语言中的应用。 实例一:指针与数组的使用 在C语言中,可以通过指针来操作数组,以下是一个简单的示例。 #include <stdio.h> int main() { int arr[5] = {1, 2, 3, 4, 5}; int *p = arr; // 指针指向数组的首地址…

    other 2023年6月25日
    00
  • 怎样深入学习python

    深入学习 Python 的完整攻略 Python 是一种强大的编程语言,应用广泛,拥有众多的库和工具。要深入学习 Python,需要遵循以下步骤: 学习基础语法:首先,应该学习 Python 的基础语法。了解 Python 的基本数据类型、变量、流程控制语句、函数、模块、类以及异常处理等方面的知识。可以通过阅读 Python 官方文档、Python 入门书籍…

    其他 2023年4月16日
    00
  • Excel如何设置减少加载项?Excel设置减少加载项教程

    Excel如何设置减少加载项?Excel设置减少加载项教程 如果你经常使用Excel,你可能已经发现Excel启动慢,这通常是因为加载了过多的插件和扩展程序。这篇文章将为你详细介绍如何设置Excel减少加载项,让Excel启动速度更快。 步骤一:打开Excel选项 首先,在Excel的主菜单中选择“文件”>“选项”。这将打开Excel选项对话框。 步骤…

    other 2023年6月25日
    00
合作推广
合作推广
分享本页
返回顶部