如何实现C语言中将两个带头节点升序链表合并？

本文共计2804个文字，预计阅读时间需要12分钟。

合并链表，顾名思义，就是将两个按顺序存储的数据的链表合并为一个链表。具体来说，就是将两个已排序的链表中的数据合并，形成一个新的链表，仍然保持数据的顺序。例如，在处理多项式加法时，需要将两个多项式对应的系数链表进行合并。

合并的方式有很多种：

合并链表，顾名思义，就是将两个按顺序存放数据的链表中的数据合并为用一个链表存储，比如在处理多项式的加减法时就需要将两个多项式的数据进行合并。合并方式有很多种：如果按照存储方式的不同，可以将两个链表的数据分别提取出来生成一个新的链表来存储原先两个链表的数据，还可以将其中一个链表的数据依次插入到另外一个链表的相应位置当中去。在遇到相同数据时可以采取只留下一个数据的方式和两个数据均保留的方式。这些不同点需要到具体的问题中具体分析，但是只是在细节上有一些差别，大体的思路都是一样的，本文主要介绍将一个链表插入到另一个链表的相应位置，插入完成后销毁链表二，且遇到相同数据采用均保留的方式。

我们还是先抛开链表的操作本身，先对两组不同的数据进行合并操作，知道两组按升序排列的数据该如何合并成一组数据，我们来分析这样几组数据（将第二组的数据插入到第一组中）：

1 5 9 13 15

2 7 12

对于这组数据我们可以很轻易的说出应该把“2”插入到“1”的前面，应该把“7”插入到“5”的前面... ... 那么我们又是如何得到这个结论的呢，接下来我们来用语言细致的描述一下我们刚才是如何得到这样的结论的：“首先，遍历第一组数据，找到第一个比要插入的数据大的数据的前一个数据“i”，再将要插入的数据插入到“i”的后面”。