题目
已知两个有序链表,试合并这两个链表,使得合并后的链表仍然有序(注:这两个链表没有公共结点,即不交叉)。
分析
既然两个链表都是有序的,所以合并它们跟合并两个有序数组没有多少区别,只是链表操作涉及到指针,不能大意。
方法一:非递归方法
使用2个指针list1和list2分别遍历两个链表,将较小值结点归并到结果链表中。如果有一个链表归并结束后另一个链表还有结点,则把另一个链表剩下部分加入到结果链表的尾部。代码如下所示:
struct node *sorted_merge(struct node *a, struct node *b) {
struct node result; //使用一个结点用于保存结果
struct node *tail = &result;
if (a == NULL) return b; //特殊情况处理
else if (b == NULL) return a;
while (a && b) {
if (a->data <= b->data) { //a链表结点值小,加入到链表尾部,并更新tail,遍历a链表下一个结点
tail->next = a;
tail = a;
a = a->next;
} else { //b链表结点值小,加入到链表尾部,更新tail,遍历b链表下一个结点
tail->next = b;
tail = b;
b = b->next;
}
}
if (a) //a结点未遍历完,则加入到尾部
tail->next = a;
if (b) //b结点未遍历完,加入到尾部
tail->next = b;
return result.next;
}
方法二:递归算法struct node* sorted_merge_recur(struct node* a, struct node* b)
{
struct node* result = NULL;
//基础情况
if (a==NULL) return(b);
else if (b==NULL) return(a);
// 递归遍历
if (a->data <= b->data) {
result = a;
result->next = sorted_merge_recur(a->next, b);
}
else {
result = b;
result->next = sorted_merge_recur(a, b->next);
}
return(result);
}
分享到:
相关推荐
有序链表合并算法动态演示系统是在B/S模式下,在MyEclipse 7.5环境中开发出来的,主要用于教学,对提高教学质量有很大的帮助。
算法-数据结构之链表合并算法.rar
将两个有序的链表合并为一个有序链表,链表的大小是可变的
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
该算法为将两个递增的链表合并为一个递减链表,采用头插法和尾插法两种不同的方法实现
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
合并链表,设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。
高效率多排序链表的合并算法,每次合并N个符合条件的结点,比传统新建表或逐个合并结点的效率要高很多,但算法相对复杂。有详细注释,可直接运行。
首先,我们需要明确问题的定义,即将多个有序链表合并为一个有序链表。这个问题的关键在于如何有效地遍历和比较链表中的元素,以实现最优的合并结果。 算法思路 针对这个问题,我们可以采用分治法的思路。首先将多个...
数据结构试验,用MFC做的,实现的是清华大学版数据结构的链表的合并的算法
两个有序链表的合并pta本文详细介绍了合并两个有序链表的算法原理、实现步骤、代码示例以及性能分析。通过掌握这一算法,我们可以更加高效地处理有序链表数据,提高程序的性能和可靠性。未来,随着数据规模的扩大和...
两个链表合并的算法,比较经典。其中一种是破坏原来的链表,另外一种是不破坏原来的链表,这里两种算法的区别就是是否需要再申请空间。
合并两个链表:设A与B分别为两个带有头结点的有序循环链表(所谓有序是指链接点按数据域值大小链接,本题不妨设按数据域值从小到大排列),list1和list2...请写出将这两个链表合并为一个带头结点的有序循环链表的算法。
数据结构 合并链表 并去除重复数据. 将LLa,LLb链表合并后存入LLc升序,输出显示,最后再去除链表中重复数据去除重复数据
求表长以及有序单链表的合并算法的实现 [问题描述] 假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并计算表长。要求利用原来两个...
设ha和hb分别是指向两个带头结点的非递减...要求设计一个算法,将这两个有序链表合并成一个非递增(递减)有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它存储空间。表中允许有重复的数据。
分别采用数组与链表,“求两个集合的合并运算”与“两个有序表合并后仍然有序”,要求编程实现。 题目一 求两个集合的合并运算 题目二 求两个有序表合并算法
数据结构与算法分析,链表的合并,相同节点只输出一个。
vc6.0 c++ 数据结构 链表的合并
合并插入排序算法(链表实现).txt