/******************************************************************
题目:输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然
是按照递增排序的。
******************************************************************/
#include<stdio.h>
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};
ListNode* createListNode(int value)
{
ListNode* pNode = new ListNode();
pNode->m_nValue = value;
pNode->m_pNext = NULL;
return pNode;
}
void connectListNode(ListNode* pListNode1, ListNode* pListNode2)
{
if(pListNode2 == NULL || pListNode2 == NULL)
return;
pListNode1->m_pNext = pListNode2;
}
ListNode* mergeSortedLists(ListNode* pList1, ListNode* pList2)
{
if(!pList1)
return pList2;
if(!pList2)
return pList1;
ListNode* pHead;
if(pList1->m_nValue <= pList2->m_nValue)
{
pHead = pList1;
pHead->m_pNext = mergeSortedLists(pList1->m_pNext,pList2);
}
if(pList1->m_nValue > pList2->m_nValue)
{
pHead = pList2;
pHead->m_pNext = mergeSortedLists(pList1,pList2->m_pNext);
}
return pHead;
}
void printList(ListNode* pNode)
{
if(pNode == NULL)
printf("List is NULL");
while(pNode)
{
printf("%d\t",pNode->m_nValue);
pNode = pNode->m_pNext;
}
printf("\n");
}
//单元测试
//两个非空链表
void test1()
{
ListNode* pList1_Node1 = createListNode(1);
ListNode* pList1_Node2 = createListNode(3);
ListNode* pList1_Node3 = createListNode(5);
ListNode* pList1_Node4 = createListNode(7);
connectListNode(pList1_Node1,pList1_Node2);
connectListNode(pList1_Node2,pList1_Node3);
connectListNode(pList1_Node3,pList1_Node4);
printList(pList1_Node1);
ListNode* pList2_Node1 = createListNode(2);
ListNode* pList2_Node2 = createListNode(4);
ListNode* pList2_Node3 = createListNode(6);
ListNode* pList2_Node4 = createListNode(8);
connectListNode(pList2_Node1,pList2_Node2);
connectListNode(pList2_Node2,pList2_Node3);
connectListNode(pList2_Node3,pList2_Node4);
printList(pList2_Node1);
ListNode* pHead = mergeSortedLists(pList1_Node1,pList2_Node1);
printList(pHead);
}
//一个空链表另一个非空
void test2()
{
ListNode* pList1_Node1 = createListNode(1);
ListNode* pList1_Node2 = createListNode(3);
ListNode* pList1_Node3 = createListNode(5);
ListNode* pList1_Node4 = createListNode(7);
connectListNode(pList1_Node1,pList1_Node2);
connectListNode(pList1_Node2,pList1_Node3);
connectListNode(pList1_Node3,pList1_Node4);
printList(pList1_Node1);
ListNode* pHead = mergeSortedLists(pList1_Node1,NULL);
printList(pHead);
}
//两个非空链表
void test3()
{
ListNode* pHead = mergeSortedLists(NULL,NULL);
printList(pHead);
}
int main()
{
test1();
test2();
test3();
return 0;
}
==参考剑指OFFER
分享到:
相关推荐
本文实例讲述了PHP实现合并两个排序链表的方法。分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 解决思路 简单的合并排序...
BM_4_合并两个排序的链表.py 是一个Python脚本,它实现了合并两个已排序链表的功能。这个脚本可用于解决合并两个已排序链表的问题,适用于需要处理链表数据结构的开发者或研究者。 内容概要: 该脚本定义了一个名...
今天小编就为大家分享一篇对python实现合并两个排序链表的方法详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
合并两个排序的链表.md
23.合并两个排序的链表1
c语言链表合并(递归和非递归实现) 包括链表创建 打印输出 通过测试,可以使用 测试环境:c-free 5.0
(1)建立两个链表A和B 链表元素个数分别为m和n个 (2)假设元素分别为 x1 x2 …xm 和 y1 y2 …yn 把它们合并成一个线性表C 使得: 当m> n时 C x1 y1 x2 y2 …xn yn … xm 当n>m时 C y1 x1 y2 x2 …ym xm ...
已有a、b两个链表,每个链表中的结点包括学号、成绩。要求把两个链表合并,按学号升序排列
实现两个链表的合并(数据结构课程设计c语言版)
合并两个有序链表OJ链接输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则解答创建一个辅助节点作为链表头节点(栈上分配)
从键盘输入两个链表,通过程序对他们排序,之后按递增顺序合并链表
我在C++程序下编辑的,希望对你们有帮助。
本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下 问题描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 struct ListNode { int val; ...
实现有序合并链表的C语言描叙的先输入两个从小到大的有序序列, 在合并后 ,也是从小到大输出。
该算法为将两个递增的链表合并为一个递减链表,采用头插法和尾插法两种不同的方法实现
剑指offer:合并两个排序的链表,Python实现 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 吐槽 本来想用递归实现,但是大脑卡壳,没有想到合适的递归...
示例 1:输入:1->2->4, 1->3->4输出:1->1->2->3->4->4因为链表是升序的,我们只需要遍历每个链表的头,比较一下哪个小就把哪个链表的