21.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

• 找出首元素更小的一个链表，让另一个链表插入其中。被插入的小链表要考虑前驱(可以new一个头结点更好处理),插入的大链表要考虑后继。

1.不采用哨兵节点

流程比较繁琐，且容器出错。思路是每次将首元素更大的链表b合并入首元素更小的链表a中。

搜索时首先找到a链表的切入点，然后遍历b链表，找到“一小段”可以直接插入的子链表。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode root,subroot;
       if(l1==null) return l2;
       if(l2==null) return l1;
        if(l1.val<l2.val){
            root=l1;
            subroot=l2;
        }
        else{
            root=l2;
            subroot=l1;
        }
        ListNode head=root,pre=root;
        while(root!=null&&subroot!=null){
            if(root.next==null){
                pre = root;
                root = root.next;
                break;
            }
            if(root.val<=subroot.val&&root.next.val>subroot.val){
                ListNode temp= subroot;
                while(temp!=null){
                    if(temp.next==null) break;
                    if(temp.next.val>root.next.val) break;
                    else temp=temp.next;
                }
                ListNode node=temp.next;

                temp.next=root.next;
                root.next=subroot;
                subroot=node;
                root=root.next;

            }
            else{
                if(root.next==null) pre=root;
                root=root.next;
            }
        }
        if(root==null){
            pre.next=subroot;
        }
        return head;
    }
}

2.采用哨兵节点优化

使用哨兵节点的思路：每次将l1和l2当前节点更小的节点，加入到当前哨兵节点的链路中。

此处prev链路相当于一个主分支，然后每次将l1和l2节点纳入到主链路中。好处在于每次插入不需要考虑l1和l2链表的前驱和后继节点。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if(l1.val<l2.val){
                prev.next=l1;
                l1=l1.next;
            }
            else{
                prev.next=l2;
                l2=l2.next;
            }
            prev=prev.next;
        }
        prev.next=l1==null?l2:l1;
        return prehead.next;
    }
}