合并两个有序链表的两种方法（带哨兵位和不带哨兵位）

一：题目

二：思路讲解

方法一：不带哨兵位

两个链表的对应节点进行比较，然后取小的尾插，直到某一个链表为空，再把剩下的不为空的链表链接过去即可。（和前面一篇博客（合并两个有序数组题目讲解-CSDN博客）思路类似）

1：应先对传过来的两个链表中存在空链表的情况，率先进行处理，list1为空，return list2，反之。

2：当一个链表比较完了之后，就没必要进行比较了，此时，另一个链表的剩余部分怎么处理，很简单，直接让排完序的那个链表的尾指针指向这个链表的剩余部分即可，因为剩下的都是大于排好序的链表里面的每一个的，而且剩余的自己也有顺序，所以直接链接即可。

代码展示：

方法二：带哨兵位

思路讲解：

哨兵位的创建 ，其意义是让新建的head和tail这两个结构体指针 指向了一个节点大小的空间，但是节点的内容和指向一开始不作任何要求，哨兵位的优势在于我们不需要在第一个尾插的时候，去进行tail和head的初次赋值。

代码展示：

一定要释放掉自己创建的哨兵位，并且让head移动到真正的头指针的位置！