《剑指offer》 第25题 合并两个排序的链表

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

思路1：用新链表

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode newList = new ListNode(-1);
        ListNode p3 = newList;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                p3.next = list1;
                list1 = list1.next;
            } else {
                p3.next = list2;
                list2 = list2.next;
            }
            p3 = p3.next;
        }

        while (list1 != null) {
            p3.next = list1;
            list1 = list1.next;
            p3 = p3.next;
        }
      //if (list1 != null)  {
      //   p3.next = list1;} 改进写法，不用一个个去复制

        while (list2 != null) {
            p3.next = list2;
            list2 = list2.next;
            p3 = p3.next;
        }
        return newList.next;
    }
}

思路2：不使用新链表，在原链表中插入

//向链表1中插入
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null ){
            return list2;
        }
        if(list2 == null){
            return list1;
        } 
        if(list1 == null && list2 == null){
            return null;
        }
        ListNode list = null;  //list是要返回的头结点，因此这里比最小值，并插入给list1
        if (list1.val > list2.val) {
            list = list1;
            list1 = list2;
            list2 = list;
        }
        list = list1;
        ListNode p = null;  //p是为了记录list1的下一个节点，避免插入时链表断开
        while (list1.next != null && list2 != null) { 
            // list1.next!=null 而不是list1!=null
//这是因此之前不仅比较了最小值，还将最小值直接给了list1，因此从list1的第二个节点开始比
//如果仅比较大小后就赋值个list，而不进行其他处理，那这里就是list1和list2比较了。
            if (list1.next.val <= list2.val) {
                list1 = list1.next;
            } else {   //在A->C中插入B（list1是A）
                p = list1.next;      // 记录要插入的List1 A的下一个节点C
                list1.next = list2;  // 插入比较小的list2的某节点B 连上A和B
                list2 = list2.next;  //list2往下走一个节点，准备下一轮比较 
                list1 = list1.next;  //将当前节点由A变成刚刚连上的B
                list1.next = p;      //将当前节点（也就是新节点）B与之前的C连上
            }
        }
        if (list2 != null) { // 最后只关心list2不为空
            list1.next = list2;
        }
        return list;
    }
}

思路3：递归
如果list1小于list2，则list1作为新序列的开头，后面应该接的部分等同于list1.next和list2的重新排序。反之同理。因此从最开始，就没有确定一定是插入到List1或者List2，而且选择较小的。

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);
            return list1; 
        }else {
            list2.next = Merge(list2.next, list1);
            return list2;
        }
    }
}