合并两个排序的的链表

题目：

​ 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。例如，输入下图中链表1和链表2，则合并之后的升序链表如链表3所示。链表节点定义如下：

public class ListNode {
    public int value;
    public ListNode next;
}

分析：

​ 链表1和链表2都是递增有序链表，所以需要把链表1的头节点和链表2的头节点比对，选择一个合并后的头节点，另外一个节点做为头节点的下一个节点；链表1的第二个节点和链表2的第二个节点也要比对，作为合并后链表的第后续节点，依此类推... 会发现，这实际上就是一个递归。

​ 每次比较两个节点的大小，把较小者放在前面，较大者放在后面；然后再把较大者和后续节点比较，依次排序。

代码：

public class MergeTowList {

    /**
     * 合并两个升序链表
     *
     * @param pHead1 链表1头节点
     * @param pHead2 链表2头节点
     * @return
     */
    public static ListNode merge(ListNode pHead1, ListNode pHead2) {

        // 链表1节点为空，说明链表1走完
        if (null == pHead1) {
            return pHead2;
        }

        // 链表2节点为空，说明链表2走完
        if (null == pHead2) {
            return pHead1;
        }

        // 合并后的头节点
        ListNode mergeHead = null;

        // 如果链表1节点的值小于链表2节点的值
        if (pHead1.value < pHead2.value) {
            // 把链表1的节点设为合并后的前一个节点
            mergeHead = pHead1;
            // 把链表1的下一个节点和链表2的当前节点比较，选出合并后链表的下一个节点
            mergeHead.next = merge(pHead1.next, pHead2);
        } else {
            mergeHead = pHead2;
            mergeHead.next = merge(pHead1, pHead2.next);
        }

        return mergeHead;
    }
}

测试：

public class TestMergeList {

    ListNode head1 = new ListNode(1);
    ListNode head2 = new ListNode(2);

    @Before
    public void init() {

        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);

        head1.next = node3;
        node3.next = node5;
//        node5.next = node7;

        head2.next = node4;
        node4.next = node6;
        node6.next = node7;
        node7.next = node8;
    }


    @Test
    public void test() {
        ListNode mergeHead = MergeTowList.merge(head1, head2);
        System.out.println(null == mergeHead ? null : mergeHead.value);
    }
}