首页 > C语言的有序单链表合并

C语言的有序单链表合并

已知两个已排序链表头节点指针headA与headB，将这两个链表合并，合并后仍为 有序的，返回合并后的头节点。

在这里插入图片描述

主要步骤如下：

  1. 创建一个临时的头节点，头节点每次指向headA 或者 headB较小的节点
  2. 当headA->data 比headB->data小的时候，headA的当前节点加入临时头节点，同时headA指针向后移动；否则headB加入临时头节点，同时headB指针向后移动
  3. 当headA或者headB链表为空的时候，将另一个不为空的节点加入临时头节点。

    在这里插入图片描述

算法实现如下：

Data *merge_list(Data *headA, Data *headB) { Data p;p.data = 0;p.next = NULL;Data *result = &p;/*构建临时头节点*/while (headA && headB) { if (headA->data < headB->data) { result->next = headA;headA = headA->next;} else { result->next = headB;headB = headB ->next;} result = result -> next;}if (headA == NULL) { result ->next = headB;} if (headB == NULL) { result ->next = headA;}return p.next;
}

递归方式更优实现如下：

class Solution { 
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == NULL) { return l2;}if (l2 == NULL) { return l1;}ListNode *head = l1 -> val < l2 -> val ?l1:l2; //取一个链表节点ListNode *nohead = l1->val < l2 -> val ?l2:l1;//保证另一个链表节点无变化head->next = mergeTwoLists(head -> next, nohead);return head;}
};

源码测试如下：

#include 
#include typedef struct Link_list
{ /* data */int data;struct Link_list *next;
}Data;/*打印链表*/
void print_list(Data *head) { while (head) { printf("%d ",head->data);head = head -> next;}printf("
");
}
/*尾插法构造链表*/
Data *insert_tail(Data *head, int n) { head = (Data *)malloc(sizeof(Data));head->next = NULL;Data *r = head;int b;while(n--){ scanf("%d",&b);Data *p = (Data *)malloc(sizeof(Data));p->data = b;r->next = p;p->next = NULL;r = p;}return head;
}
/*合并有序链表*/
Data *merge_list(Data *headA, Data *headB) { Data p;p.data = 0;p.next = NULL;Data *result = &p;while (headA && headB) { if (headA->data < headB->data) { result->next = headA;headA = headA->next;} else { result->next = headB;headB = headB ->next;} result = result -> next;}if (headA == NULL) { result ->next = headB;} if (headB == NULL) { result ->next = headA;}return p.next;
}int main(){ Data *headA,*headB;printf("construct first list : 
");//尾插法构造一个五节点的链表headA = insert_tail(headA,5);printf("construct second list :
");//尾插法构造一个三节点的链表headB = insert_tail(headB,3);Data *result = merge_list(headA->next,headB->next);printf("merge the list :
");print_list(result);return 0;
}

输出如下：

construct first list : 
1 4 5 6 7
construct second list :
5 6 7
merge the list :
1 4 5 5 6 6 7 7

更多相关：

  • 剑指offer：面试题25. 合并两个排序的链表

    题目：合并两个排序的链表 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制： 0 <= 链表长度 <= 1000 解题: /*** Definition for singly-linked li...

  • 剑指offer：面试题24. 反转链表

    题目：反转链表 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制： 0 <= 节点个数 <= 5000 解题： 方法一：双指针 我们可以申请两个指针，第一个指针叫 new_next，最...

  • LRU算法 -- 链表 完整实现

    LRU算法(Least Recently Used) 算是我们经常遇到的一种淘汰算法，其中内存管理模块进行内存页回收时有用到，针对不经常使用的内存页，LRU淘汰策略能够将该内存页回收给操作系统。 属于 我们操作系统设计中的 时间局部性原理，最长时间未被访问的数据优先淘汰，当内存中已存在的数据再次被访问时，则进行热度的提升。 本文为...

  • leetcode-24 两两交换链表中的节点

    题目描述 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->4, 你应该返回 2->1->4->3. 方法一（递归）： 将配对交换过程拆解为多个以两个元素为一对的子问题 …n(k-1) -> n(k)->n(k+1)...

  • python制作统计图_刻意练习11：Python描述统计、简单统计图形

    学习计划 MyPlan11 主题：Python描述统计、简单统计图形 时间：8.5-8.11周内完成 参考资料：新书《谁说菜鸟不会数据分析python篇》 各位星友们，在这个星球里每个人都要逼迫自己学习未知的领域或知识点，每天进步一点点，积累的时间久了 ，菜鸟也能起飞。 完成情况： 在pandas中，使用describe函数进行描述统...

  • python3socket非阻塞_利用Python中SocketServer 实现客户端与服务器间非阻塞通信

    利用SocketServer模块来实现网络客户端与服务器并发连接非阻塞通信。 首先，先了解下SocketServer模块中可供使用的类： BaseServer：包含服务器的核心功能与混合（mix-in）类挂钩；这个类只用于派生，所以不会生成这个类的实例；可以考虑使用TCPServer和UDPServer。 TCPServer/UDPS...

  • 剑指offer：面试题37. 序列化二叉树

    题目：序列化二叉树 请实现两个函数，分别用来序列化和反序列化二叉树。 示例:  你可以将以下二叉树：     1    /   2   3      /     4   5 序列化为 "[1,2,3,null,null,4,5]" 解题： /*** Definition for a binary tree no...

  • sd.js 2.0封装：更加简化请求传参内容

    sd.js  import $global from "./global"; import $g from "./sg"; import $ from "jquery"; import {Message, Loading} from "element-ui";//引入饿了么相关组件 import {Base64} from "js-...

  • sd.js帮助您简化繁重的获取数据、存储数据（CRUD）骚操作（吐槽~在安卓9.0以下或者IOS10.X以下手机端H5页面不支持，在这两

        原生sd.js----------------------------------------------------------------  const API_ROOT_URL = "http://www.api.com";const $d= {_postList_url: API_ROOT_URL + "/api...

©2024 11GX.COM