算法（16）合并两个排序的链表

题目描述

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

随着做题越来越感觉递归可以让复杂的问题简单话，我们只需要清楚最根本的操作之后，递归帮你做了重复的事情。拨开云雾见本质。

我们最基本的操作就是两个节点进行比较，对于值小的进行赋值，然后移到后面的节点，再进行比较。以此类推，直到一个为null。也就是比较节点的移动。

  public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode newList = null;

        if (list1.val <= list2.val) {
            newList = list1;
            newList.next = Merge(list1.next, list2);
        } else {
            newList = list2;
            newList.next = Merge(list1, list2.next);
        }


        return newList;

    }