合并两个排序的链表【Java版】

1）朴素方法

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //没有虚拟头结点的坏处：要额外拎出来头部的过程，而不是统一
        if(list1 == null)return list2;
        if(list2 == null)return list1;
        ListNode p0 = null;//标记头部，不能动
        if(list1.val < list2.val){
            p0=list1;
            list1=list1.next;
        }
        else{
            p0=list2;
            list2=list2.next;
        }
        ListNode p=p0;
        while(list1 != null && list2 != null){//正式主体过程
            if(list1.val < list2.val){
                p.next=list1;
                p=p.next;//【千万别漏了这个】
                list1=list1.next;
            }
            else{
                p.next=list2;
                p=p.next;
                list2=list2.next;//直接修改题目变量，可节约空间
            }
        }
        if(list1==null)p.next=list2;
        if(list2==null)p.next=list1;
        return p0;
    }
}
// 时间 O(N),  空间 O(1)

2）虚拟头结点：统一过程&精简代码

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //建立虚拟头结点，可以统一过程&精简代码，同时减少或不用考虑头部的情况
        //此代码和上面相比，只有函数里的第一行和最后一行是修改的
        ListNode vHead = new ListNode(Integer.MIN_VALUE);//建立虚拟头结点  //建立的时候不能用null,必须实例化
        ListNode p=vHead;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next=list1;
                p=p.next;
                list1=list1.next;
            }
            else{
                p.next=list2;
                p=p.next;
                list2=list2.next;
            }
        }
        if(list1==null)p.next=list2;
        if(list2==null)p.next=list1;
        return vHead.next;//虚拟头结点一直在那不动,返回它的下一个即为第一个真实节点
    }
}