/******************************************************************
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然
是按照递增排序的。
******************************************************************/
#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
这个问题可以通过递归或迭代的方法来解决，这里我们将重点讨论基于合并两个有序链表的解决方案。 首先，我们需要了解链表的基本结构。在 C++ 中，链表节点通常定义为一个结构体或类，包含一个整数值 `val` 代表节点...
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 ...
在本文中，我们将深入探讨如何将两个无序的链表合并为一个有序链表，同时也会涉及MFC（Microsoft Foundation Classes）的可视化编程技术。在实际的编程环境中，链表是一种常用的抽象数据类型，用于存储一系列元素，...
"java编程题之合并两个排序的链表" 本文主要介绍了java编程题之合并两个排序的链表，以供大家参考。下面是对该知识点的详细说明： 链表基本概念 在计算机科学中，链表是一种基本的数据结构。它是一种动态的数据...
当提到“两个有序链表的合并PTA”时，这通常意味着在PTA平台上解决一个特定的问题，即合并两个有序链表。具体任务可能是给定两个已按升序排序的链表，要求编写代码来合并这两个链表，形成一个新的有序链表。
已有a、b两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列
合并两个有序链表的目的是创建一个新的有序链表，保持原有的顺序。这个过程通常比单独排序两个链表更有效率，因为链表已经部分有序。 清华大学版数据结构教材中的链表合并算法通常采用迭代或递归的方式。这里我们...
从键盘输入两个链表，通过程序对他们排序，之后按递增顺序合并链表
实现两个链表的合并(数据结构课程设计c语言版）
合并两个有序链表OJ链接输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则解答创建一个辅助节点作为链表头节点（栈上分配）
8. MergeListAB：这个文件可能是演示系统的一部分，具体用途可能是一个示例输入，用于展示如何合并两个有序链表A和B。 通过这个系统，学生和教师可以深入理解有序链表合并算法的细节，同时体验到B/S模式带来的便利...