合并两个排序的链表

《剑指offer》面试题25：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路一：归并排序的思想（非递归方式）

代码如下：

public ListNode merge1(ListNode list1,ListNode list2) {
    if (list1 == null) {
        return list2;
    } else if (list2 == null) {
        return list1;
    } else {
        ListNode node1 = list1;
        ListNode node2 = list2;
        // 确定合并后的新链表的头节点
        ListNode mergeHead = null;
        if (node1.val > node2.val) {
            mergeHead = node2;
            node2 = node2.next;
        } else {
            mergeHead = node1;
            node1 = node1.next;
        }
        // 归并的过程
        ListNode curNode = mergeHead;
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                curNode.next = node2;
                node2 = node2.next;
            } else {
                curNode.next = node1;
                node1 = node1.next;
            }
            curNode = curNode.next;
        }
        // 有一个链表归并完，另一个链表剩余的节点接上
        if (node1 == null) {
            curNode.next = node2;
        }
        if (node2 == null) {
            curNode.next = node1;
        }
        return mergeHead;
    }
}

思路二：每次比较两个节点的val的大小实际是重复的过程，可以借助递归函数实现。

代码如下：

public ListNode merge2(ListNode list1,ListNode list2) {
    if (list1 == null) {
        return list2;
    } else if (list2 == null) {
        return list1;
    } else {
        ListNode mergeHead = null;
        if (list1.val > list2.val) {
            mergeHead = list2;
            mergeHead.next = merge2(list1,list2.next);
        } else {
            mergeHead = list1;
            mergeHead.next = merge2(list1.next,list2);
        }
        return mergeHead;
    }
}