单链表之合并两个有序单链表

题目说的是：合并两个有序的单链表，两个链表既然都有序，那其实我们要做的工作就不是很多了，如果两个链表是无序的，那我们还需要各自对两个链表进行排序再进行合并的操作。

思路一：遍历实现

这种实现方式思路比较清晰，代码也比较容易理解，但是较为冗长，我自己没有进行实现，大家可以点击链接去作者的博客了解一下。

思路二：递归实现

不得不说递归的实现方法真的太巧妙了， 几行代码解决问题。递归比较考验我们的抽象问题的能力。

关于递归，有以下几个要点：1. 问题可以分解为多个相同的小问题。2. 每个小问题的处理方式一样的。

比如我们在电影院，想自己在第几排，那我们可以问前一排的人他在第几排，我们+1就可以了，但是他也不知道在第几排，所以他又去问他前面的人，这样一个接一个问到第一排的人，再一个个返回来。就知道自己第几排了。这就是递归的思路。

合并两个单链表，无非就是不断比较他们当前的节点，将大的（或小的）一个，链接到新的链表上。这里很好的运用了递归把大问题化解成N个小的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 使用递归从开始比较两个链表，放入新的链表
 * @param h1
 * @param h2
 * @return
 */
public static ListNode mergeTwoLinkedList(ListNode h1, ListNode h2) {
    // 这两个属于递归终止条件
    if (h1 == null) {
        return h2;
    }
    if (h2 == null) {
        return h1;
    }
    
    ListNode head = null;
    if (h1.val <= h2.val) {
        head = h1;
        head.next(mergeTwoLinkedList(h1.next, h2));
    }else {
        head = h2;
        head.next(mergeTwoLinkedList(h1, h2.next));
    }
    return head;
}

算法专栏的王争老师在递归这节课中有一句话说的很好：不要试图去详细分析递归的运行过程。 研究过递归代码的同学应该都深有体会，稍稍复杂一点，就很容易看晕，放心，这不是因为我们脑容量不够或者比较笨！