合并两个排序的链表

问题陈述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：0 <= 链表长度 <= 1000

思路分析

• 先判断是否L1、L2为空。

• 比较L1，L2的值，小的加入新链表mergeLinklist。

• 当一方已经为空，是否另一方还有未比较的元素，然后直接加入mergeLinklist。

代码实现

public class Merge_Two_Linklist {
    public ListNode mergeTwoLinklists(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;

        ListNode mergeLink_head=new ListNode(0);
        ListNode mergeNode=mergeLink_head;//mergeNode在判断过程中会不断往下走，因此需要定义mergeLink_head指向初始结点。
        while (l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                mergeNode.next=l1;//使用了l1，那么l1遍历到下一个位置。
                l1=l1.next;
            }else {
                mergeNode.next=l2;
                l2=l2.next;
            }
            mergeNode=mergeNode.next;
        }
        mergeNode.next=l1==null?l2:l1;
        return mergeLink_head.next;
    }
        public static void main(String[] args){
        ListNode l1=new ListNode(3);
        l1.next=new ListNode(6);
        l1.next.next=new ListNode(9);
        ListNode l2=new ListNode(2);
        l2.next=new ListNode(5);
        l2.next.next=new ListNode(8);
        Merge_Two_Linklist merge_two_linklist=new Merge_Two_Linklist();
        merge_two_linklist.mergeTwoLinklists(l1,l2);
    }
}