剑指offer系列之十五：合并两个排序的链表

题目描述

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

这道题我的第一思路这样的：可以先遍历这两个排序的链表，把遍历的结果存放在一个集合中，然后调用库函数Arrays.sort方法完成排序，之后，根据这些排好序的结果重新创建一个链表，即为合并之后但仍然排序的链表。但是这种思路需要额外的List和创建链表的空间开销，而且时间复杂度最快也是O(nlogn)。所以不是很理想。第二种思路是这样的：因为两个链表都是排序的，所以可以先比较两个链表的头结点，这样就确定了合并之后链表的第一个节点，之后再比较两个链表的第二个节点（原来较大值与较小值所属链表的第二个节点进行比较），这样依次就能确定合并链表的第二个、第三个节点，故明显是一个递归的过程。参照这个过程实现代码如下（已被牛客AC）：

package com.rhwayfun.offer;

public class MergeLinkedList {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

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

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

        return mergeListHead;
    }

}

上面的递归代码看起来很简洁，但是非递归代码也是需要掌握的，代码如下：

public ListNode Merge2(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode mergeList = null;
        ListNode curNode = null;

        //初始化第一个节点
        if(list1.val < list2.val){
            curNode = list1;
            list1 = list1.next;
            curNode.next = null;
            mergeList = curNode;
        }else{
            curNode = list2;
            list2 = list2.next;
            curNode.next = null;
            mergeList = curNode;
        }

        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                curNode = list1;
                list1 = list1.next;
                curNode.next = null;
                mergeList.next = curNode;
                mergeList = mergeList.next;
            }else{
                curNode = list2;
                list2 = list2.next;
                curNode.next = null;
                mergeList.next = curNode;
                mergeList = mergeList.next;
            }
        }

        //处理剩余的结点
        while(list1 != null){
            curNode = list1;
            list1 = list1.next;
            curNode.next = null;
            mergeList.next = curNode;
            mergeList = mergeList.next;
        }
        while(list2 != null){
            curNode = list2;
            list2 = list2.next;
            curNode.next = null;
            mergeList.next = curNode;
            mergeList = mergeList.next;
        }

        return mergeList;
    }