数据结构——有序链表合并（C语言版）

有序链表合并

两个有序的链表，要求将其合并为一个链表，并且该链表保持有序！！

这里所讲的是链表升序！

首先，我们要构造两张按照升序排列好的链表。
构造链表：我们的方法有尾插，头插，大家可以click链接来查看：
https://blog.csdn.net/code_zx/article/details/80024207

这里我们的实验数据，以及思路如图所示！！
实验数据：
链表1：1， 3， 5， 7
链表2：1， 2， 4 ，5

关于合并的部分代码！

// 合并两个有序单链表，合并后依然有序 (升序)
PNode MergeSList(PNode pHead1, PNode pHead2)
{
    if (pHead1 == NULL && pHead2 == NULL)
    {
        return NULL;
    }

PNode pNewHead = NULL;
PNode pCur1 = pHead1;
PNode pCur2 = pHead2;
PNode pCur = NULL;

if (pCur1->_data > pCur2->_data)             //选择头结点
{
    pNewHead = pCur2;
    pCur2 = pCur2->_pNext;
}
else
{
    pNewHead = pCur1;
    pCur1 = pCur1->_pNext;
}

pCur = pNewHead;
while (pCur1 && pCur2)                   //当pCur1 以及 pCur2 均不为空时  进入循环
{
    if (pCur1->_data < pCur2->_data)     //循环中选择data较小的结点链接到pcur的后面
    {
        pCur->_pNext = pCur1;
        pCur1 = pCur1->_pNext;
        pCur = pCur->_pNext;
    }
    else
    {
        pCur->_pNext = pCur2;
        pCur2 = pCur2->_pNext;
        pCur = pCur->_pNext;
    }
}

if (pCur1 == NULL)                    //出循环之后，将非空的链表直接接到pcur的后面
    pCur->_pNext = pCur2;
else
    pCur->_pNext = pCur1;

return pNewHead;
}

该代码中有许多可以优化的地方！
譬如，可以将选择头结点或者循环链接的操作进行一个有效的封装
大家可以试一试！！

另外，可以采用分离链表元素的方式，用数组进行排序，再进行链表与数组之间的转化，最终达到合并链表的功能！
之前用数组做过一次，可以参考一下：https://blog.csdn.net/code_zx/article/details/80886366

关于数据结构的其他知识大家可以访问我的主页！

没有敲不坏的键盘！！！！只要你敢敲！！！
谢谢！