合并两个有序链表,合并后依然有序 _链表

合并两个有序链表合并之后还是有序的，首先这两个链表是需要是有序的，也就是说这两个链表已经排好序了，才能进行合并。但是昨天也写过冒泡排序的程序了，如果让你合并两个不是有序的链表合并之后有序，那可以先将两个链表进行冒泡排序再进行合并就可以了。
首先明确思路，合并两个链表有两种方式，第一种就是创建一个新的链表，不断的将原来两个链表的数据接入新的链表，但是还有另外一种方式就是在原来两个链表上进行操作，将其中一个链表的数据不断的和另一个链表的数据进行比较，如果第一个链表的数据比第二个大的话那就将第二个链表的数据放在第一个链表当前数据的前边，今天我所写的代码是第一种的方式，第一种相对来说容易理解，并且容易操作。
SListNode* SListMerge(SListNode* list1, SListNode* list2){SListNode *New=BuySListNode(0);SListNode*head=New;while (list1&&list2 ){if ((list1->_data) < (list2->_data)){SListPushBack(&New,list1->_data );list1 = list1->_next;}else{SListPushBack(&New, list2->_data);list2 = list2->_next;}}if (list1 == NULL){while (list2){SListPushBack(&New, list2->_data);list2 = list2->_next;}}if (list2 == NULL){while (list1){SListPushBack(&New, list1->_data);list1 = list1->_next;}}return head;}
先看一下代码。上来首先判断是不是会有传入的两个链表为空的情况。
while(list1&&list2)
{
if((list1->_data) < (list2->_data))
{
(&New,list1->_data );
list1=list1->_next;
}
else
{
(&New, list2->_data);
list2=list2->_next;
}
}
之后进入while循环如果有一个链表为空的话就需要结束循环，进入循环之后两个节点的数据进行比较，将其中小的那个的数据通过尾插函数将数据插入新的链表中，之后传入数据的那个链表的指针就需要向后移动一个。
if(list1== NULL)
{
while(list2)
{
(&New, list2->_data);
list2=list2->_next;
}
}

文章插图
if(list2== NULL)
{
while(list1)
{
(&New, list1->_data);
list1=list1->_next;
}
}
如果跳出while循环，不排除会存在其中一个为空，但是另一个还没走到链表最后的情况，所以需要将非空的那一个链表剩下的数据再次通过尾插插入新的链表中。
之后返回新链表的头指针，就可以了。

void SListPushBack(SListNode** ppHead, DataType x){SListNode *cur = NULL;SListNode *NewNode;cur = *ppHead;NewNode = BuySListNode(x);if (*ppHead == NULL){*ppHead = NewNode;(*ppHead)->_next = NULL;}else{while (cur->_next){cur = cur->_next;}cur->_next = NewNode;NewNode->_next = NULL;}}

SListNode* BuySListNode(DataType x){SListNode *NewNode;NewNode = (SListNode*)malloc(sizeof(SListNode));if (NewNode == NULL){printf("空间分配失败\n");}else{NewNode->_data = http://www.kingceram.com/post/x;NewNode->_next = NULL;}return NewNode;}

这两个分别是尾插函数和分配空间的函数。
【合并两个有序链表,合并后依然有序】

文章插图