引子：五分钟玩转面试考点-数据结构系列，不会像那种严肃、古板的教科书般的博客文章，而是将晦涩难懂的概念和知识点尽可能幽默的细说出来，或结合生活场景，或从零开始分析。带给大家一个严肃而不失风趣的数据结构。

---

下面是一道笔试题：

题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

当看到这个问题的时候，脑子里是不是不由的回想到归并排序？
那好吧，咱们就开始分析吧：

两个有序链表合并成一个有序链表。

1. 首先咱们需要新创建一个链表吧，什么头节点怎么解决？

解决办法1：头结点我们可以随便设置一个数，但是我们的返回值可以设置为root.next，是不是就完美避开了头结点？当然有点取巧的嫌疑了。

解决办法2：我们可以将两个链表最小的节点设置为头结点，然后两个链表进行比较。这个是咱们最开始想到的办法。

1. 迭代法

大致说一下，就是新创建一个节点，其实本质上是两个节点，一个保存头结点信息，一个当做指针，创建链表。

当两个链表都不为空的情况下，新链表指向将两个链表中的小节点，也就是：root.next=list1。并且root指针要前进一位root=list1（list1是Root最新位置）。(PS：小悠同学举手说：链表list1也需要前进一位的呀！即list1=list1.next)

此时，不得不说小胖同学很年轻，我贴出我遇到的问题吧：

年轻的小胖犯的错.png

小胖却妄想：使用node输出新链表的头指针！大家可以找找小胖少些了那句代码?

  //合并有序链表（递归法）
    public static ListNode Merge(ListNode list1, ListNode list2) {
        //极限条件
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        //创建链表(此节点需要保存，用于输出)
        ListNode node = null;
        //root节点负责移动
        ListNode root = node;
        //开始相互比较
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                //判断root是否为null
                if (root == null) {
                    root = list1;   //list1作为头结点
                    node=root;   //---》年轻的小胖犯的错
                } else {
                    //root指向list1（下一个位置）
                    root.next = list1;
                    root = list1;   //root指针全局一位
                }
                //list1前进一位
                list1 = list1.next;
            } else {
                if (root == null) {
                    root = list2;
                    node=root;
                } else {
                    root.next = list2;
                    root = list2;
                }
                list2 = list2.next;
            }
        }
        if(list1==null){
            root.next=list2;
        }
        if(list2==null){
            root.next=list1;
        }
        return node;
    }

---

2. 递归法

上面说的那么多，根本没有到这篇文章的重点，自从小胖同学学了递归之后，对递归很是着迷。所以，总有一些不成熟的小总结，你看，我的总结又来了...

小胖开始写代码了，此时，我知道一个方法会返回给我一个有序链表，我要做的就是将一个节点加到方法返回值上。什么？怎么执行方法的？小胖并不关心呀。

1. 首先我调用Merge()方法，一定返回给我一个最小链表的头结点，我只需要将最小节点指向这个链表（头插法）然后返回就行了。

  /**
     * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        //极限条件
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        //返回值，是一个新的链表，我调用这个方法，会给我一个单调递增的链表。我第一次调用调用这个方法时
        if (list1.val < list2.val) {
            list1.next = Merge(list1.next, list2);
            //最开始的元素是谁？list1？
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }

递归书写，先假设这个方法可以返回正确的结果，主要完成第一次执行。