剑指offer第三天-----合并两个排序的链表

剑指offer第三天-----合并两个排序的链表

这道题拿到首先想到了归并排序，依然是垃圾，细节好多没处理，看到空间复杂度O（1）就不敢再创另一个队列变量，而且在做非递归写法的时候，不会返回新队列的头结点，和前几题的毛病一样。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head=null;   //新队列头结点
        ListNode temp= null;   //很关键！ 辅助结点 用来后面遍历的
       
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){ 
               if(head==null) {head=temp=list1;list1=list1.next;} //这一步既保住了头结点又保住了temp可以顺利遍历
                else{temp.next=list1;list1=list1.next;temp=temp.next;}//改的从来都是temp的下一个 不是temp
            }
            else{if(head==null) {head=temp=list2;list2=list2.next;}
                else{temp.next=list2;list2=list2.next;temp=temp.next;}}
        
                    
        }if(list1!=null){if(head==null) {head=list1;} else{temp.next=list1;}} //这里又加一个头结点判断是为了防止输入的list有空的现象
            if(list2!=null){if(head==null) {head=list2;}else{temp.next=list2;}}
        return head;
    }
}

 这里写代码的时候 经常有几个地方报错

1. 如果先声明head为null，就不能指定他的next也为null，不然会报错

   请检查是否存在数组越界等非法访问情况

   java.lang.NullPointerException

2. 遍历的节点只能是temp的下一个  如head=temp=list1; 要想在后面遍历只能是temp.next=什么什么（temp的next就是head的next），不能是temp=temp.next;temp=什么什么，这样会导致断链，head与temp脱节   

也就是说 非递归方法要保留头结点 用一个if（头点为空）{赋值头结点与遍历节点，让其连接}else{遍历节点的 下一个去添加值继续遍历} 

递归解法

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
            if(list1==null){return list2;}// 递归出口
            if(list2==null){return list1;}
            if(list1.val<=list2.val){
                list1.next=Merge(list1.next,list2); //用本身的list就是为了不断链
                return list1;
            }else{
                list2.next=Merge(list1,list2.next);
                return list2;
            }
    }
}

这个递归就是不断的比较 不断的往深找最小的，但是在返回的时候需要注意一下，他最深处返回是最大值，而且这道题是要一个列表。在返回的时候就一定是一个列表，而不是一个点。

而且这个列表不能是凭空捏造的辅助点，必须是自身的点。这样才能保证当前的点与后面的点连接（不会断链）。

注意关于链表问题的常见注意点的思考：

1、如果输入的头结点是 NULL，或者整个链表只有一个结点的时候

2、链表断裂的考虑

i小宋