No.21  合并两个有序链表

题目 ：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 ：

输入：1->2->4, 1->3->4输出：1->1->2->3->4->4

分析 ：这题目很简单 ，而且前边关于链表关于排序都有过类似的题目 ，有遗忘的可以回头看看 记录帖 | Leetcode打卡目录（NO.1-20）

思路一 ：利用链表已经有序 ，创建一个新链表 ，从头指针开始 ，将两个链表依次比较 ，新目标链表指向比较后较小的链表（记作A）的对应节点值 ，然后将该链表A后移一个节点重复操作 。直到有个链表已经移动到最后 ，此时将另一个链表接到目标链表后即可 ，小詹记得前边有一题特别类似 。具体代码实现如下 ：

思路二 ：除了上述思路 ，还可以利用递归思路 ，我们注意到链表指针指向后边的还是一个链表 ，可看作少一个节点的链表 。于是我们可以考虑反复调用该方法 ，只是将参数改成去除一个节点的链表和另一个没有变化的链表即可 ，具体代码如下 ：

而且提交表明 ，思路二的速度快很多 ，小伙伴们可以自行try一try哦 ~