题解 | #合并两个排序的链表#

递归思路

同Leetcode 21 Merge Two Sorted Lists ，用递归实现：

简单地理一下思路：

• 从头结点开始考虑，比较两表头结点的值，值较小的list的头结点后面接merge好的链表（进入递归了）；
• 若两链表有一个为空，返回非空链表，递归结束；
• 当前层不考虑下一层的细节，当前层较小的结点接上该结点的next与另一结点merge好的表头就ok了；
• 每层返回选定的较小结点就ok；

重新整理一下：

• 终止条件：两链表其中一个为空时，返回另一个链表；
• 当前递归内容：若list1.val <= list2.val 将较小的list1.next与merge后的表头连接，即list1.next = Merge(list1.next,list2); list2.val较大时同理；
• 每次的返回值：排序好的链表头；

复杂度：O(m+n) O(m+n)

递归实现

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }
        else if(list2==null){
            return list1;
        }
        if(list2.val>list1.val){
            list1.next = Merge(list1.next,list2);
            return list1;
        }
        else{
            list2.next = Merge(list1,list2.next);
            return list2;
        }
    }
}

空间O(1)的思路：

• 创建一个虚拟结点和一个哨兵结点

• 当list1与list2都不为null时循环

• 哪个的val小哪个赋给虚拟结点的next，虚拟结点后移。

• 退出循环后，哪个list不为空，哪个结点（包括剩下的）给虚拟结点的next

• 最后返回哨兵结点的next

实现：

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode res = dummy;
        // 必须保证两个list都不为空
        while(list1 != null & list2 != null) {
            if(list1.val > list2.val) {
                dummy.next = list2;
                list2 = list2.next;
                dummy = dummy.next;
            } else if(list1.val <= list2.val) {
                dummy.next = list1;
                list1 = list1.next;
                dummy = dummy.next;
            }
        }
        // list1后面还有，就把剩下的全部拿走
        if(list1 != null) {
            dummy.next = list1;
        }
        if(list2 != null) {
            dummy.next = list2;
        }
        return res.next;
    }
}