25-合并两个排序的链表

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

第一种 普通方法

使用一个dummy结点，然后比较两个链表的当前结点，小的加入到新链表中，依次比较，直到其中一个链表为空，然后把非空的链表加入到新链表里。

public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        ListNode head = new ListNode(0);//dummy node
        ListNode p = head;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                p.next = list2;
                list2 = list2.next;
                p = p.next;
            }else{
                p.next = list1;
                list1 = list1.next;
                p = p.next;
            }
        }
    	p.next = list1 == null ? list2 : list1;
        ListNode res = head.next;
        head.next = null;
        return res;

    }

第二种 递归方法

这种方法就很高级了，使用递归的思路。 “To Iterate is Human, to Recurse, Divine.”中文译为：“人理解迭代，神理解递归。” 先看代码吧

public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }

和第一种方法比起来，有点云泥之别的感觉，太简洁！！ 多理解，多理解。 递归基本需要以下三个条件

1. 递归结束的条件

2. 缩小问题规模同时不重叠

3. 问题结果如何结合成最终结果。

第三个问题总是不容易搞定。多思考多练习吧