单链表的归并算法思路总结

刚在练习的时候需要将两个递增有序的单链表进行归并处理，之前碰到这种问题，心里总是有些害怕，害怕自己不能完全考虑到所有的情况，怕自己想不明白里面的流程，怕自己做不到。。。

但是，我慢慢理解并深以为然的是：越动手去做，越得心应手。

好像应了那句，越努力越幸运。

很多情况下，生活中的其他场景里，我能够很自然，自信的去思考，去行动，但是对应到程序世界里来，就有些畏手畏脚。明明背后的逻辑，需要的领域知识，自己全都能够灵活应用，却偏偏不敢动手写代码。

我不知道你是不是曾经或者现在也有这样的困惑。这花费了我许久的时间去想通。

OK，我们还是主要聊这段代码如何从自然的归并思路平滑转换到代码中。

先看题目：

假设两个递增有序的线性表，均以单链表形式存储。将两个单链表归并为按元素递减次序排列的单链表，并要求：利用原来的结点存储。

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;
typedef int ElemType;
#define MAX 100

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node, *List;
// 生成一个链表，数值随机生成
// 返回指向生成链表的头结点指针
List generateList(int n)
{
    srand(n);
    // 定义头结点
    List Head = (List)malloc(sizeof(Node));
    Head->next = NULL;
    Node *temp = Head; //使用temp拿着L的位置，为的是不改变L的数值
    // 先通过vector建立一个递增有序的数列
    vector<int> ins;
    for(int i = 0; i < n; i++)
    {
        int x = rand() % MAX;
        ins.push_back(x);
    }
    sort(ins.begin(), ins.end()); 

    //尾插法建立链表
    for(int i = 0; i < n; i++)
    {
        Node *s = (Node*)malloc(sizeof(Node));
        s->data = ins[i];
        s->next = NULL;

        temp->next = s; 
        temp = s;
    }
    return Head;
}
void mergeList(List &H1, List &H2)
{
    // 两个递增 ==》 一个递减
    // 思路：采用头插法进行
    // 用两个指针p,q分别跟踪
    // 如果p指向的结点较小，就插入并将p往后移动，否则将q插入并移动
    // 当一方结点为空了，就将对方的结点依次头插法插入链表直到结束
    List m = (List)malloc(sizeof(Node));
    m->next = NULL;
    Node *p = H1->next;
    Node *q = H2->next;
    while(p && q)
    {
        if(p->data <= q->data)
        {
            Node *temp = p->next;// 暂存
            p->next = m->next;
            m->next = p;
            p = temp;
        }
        else
        {
            Node *temp = q->next;
            q->next = m->next;
            m->next = q;
            q = temp;
        }
    }
    while(p)
    {
        Node *temp = p->next; // 注意一定要用temp暂存，总是会不注意p->next 已经被更改了，从而陷入死循环
        p->next = m->next;
        m->next = p;
        p = temp;
    }
    while(q)
    {
        Node *temp = q->next;
        q->next = m->next;
        m->next  = q;
        q = temp;
    }
    H1 = m;
}
int main()
{
    // 两个递增的单链表
    // 合并成一个递减的单链表
    // 且为了节省空间，只是修改链接
    int n,m;
    cout << "Input two numbers of nodes: ";
    cin >> n >> m;
    List H1 = generateList(n);
    List H2 = generateList(m);

    Node *p = H1->next; //指向第一个结点
    while(p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
    Node *q = H2->next; //指向第一个结点
    while(q)
    {
        cout << q->data << " ";
        q = q->next;
    }
    cout << endl;
    // 题目的主要逻辑
    mergeList(H1,H2); // 返回的是H1指向的合并好的链表

    // 输出合并后的结果
    p = H1->next;
    while(p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
    return 0;
}

如何构建一个单链表这里不会再详细解释，假设已经建好，且如题要求的递增顺序。

这里主要关注的是如何归并。

    // 思路：采用头插法进行
    // 用两个指针p,q分别跟踪
    // 如果p指向的结点较小，就插入并将p往后移动，否则将q插入并移动
    // 当一方结点为空了，就将对方的结点依次头插法插入链表直到结束

这段注释其实就完全阐述了如何归并。所以思路非常清晰，转换为代码的过程，就个人体会而言，重点是记住要暂存结点，这是导致写出死循环的一大原因。

首先是：我们新建个头部用于导航合并的链表，结束后把值给H1.

    List m = (List)malloc(sizeof(Node));
    m->next = NULL;
    Node *p = H1->next;//指向工作结点
    Node *q = H2->next; //指向工作结点

头插法中p和q都不空的情况：

 while(p && q)
    {
        if(p->data <= q->data)
        {
            Node *temp = p->next;// 暂存
            p->next = m->next;
            m->next = p;
            p = temp;
        }
        else
        {
            Node *temp = q->next;
            q->next = m->next;
            m->next = q;
            q = temp;
        }
    }

用temp暂存的原因是，，头插法时当前结点p或者q的next域要指向头指向的那个结点。因此，p或q的下一个结点就要被p或q放下了，这个不能忽视，因此，需要暂时存着，p和q跟踪的就是工作结点，他们后面的结点在下一轮就是工作结点了！

而当p或者q其中一个已经为空后，对方还拿着那个没插入的结点，因此在下面的后续处理中，我们只看一种p还没空的状态：

while(p)
{
    Node *temp = p->next; // 注意一定要用temp暂存，总是会不注意p->next 已经被更改了，从而陷入死循环
    p->next = m->next;
    m->next = p;
    p = temp;
}

此时从p指向的结点开始，一个一个往头结点后面插入即可。注意仍然需要暂存p之后的结点，解释和上面的相同。

到这里，可见归并单链表并不难理解，甚至非常简单自然。
但是，只有当你自己动手做到而不只是看懂然后默念，哦原来这么简单的时候，才是你真正理解掌握的时候。

对，还想分享一段我读来差点哭泣的话，以缅怀那些烦恼的日子，告诫我：烦恼即菩提，心无挂碍，才会安然活在当下，不惊不怖不畏。

“世界上在忧虑的人永远不会是天才或者是庸人，而是介于这两者之间的人。这些人有点儿小聪明，却又不够聪明。不懒，但也不够勤奋。他们就这样在自己的位置上来回走动。这样的人是痛苦的，一生都会活在某种无形的枷锁之中。”

“行动其实就是打开枷锁的钥匙。”

以上，愿有同感的人共勉。

最后

以上就是务实烤鸡为你收集整理的单链表的归并算法思路总结的全部内容，希望文章能够帮你解决单链表的归并算法思路总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。