leetcode21合并两个有序链表

题目：

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

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

---

解决：

解法1：循环+双指针

用示例一来演示，引入结果节点P，对l1和l2的头节点进行比较，1=1，优先把l2的节点挂到结果中，l2指针后移。再比较l1的1和l2的3，1<3，则把l1的节点挂到结果中，l1指针后移。2<3，则把l1的2挂到结果中，l1指针后移。4>3，则把l2的3挂到结果中，l2指针后移。4=4，把l2的节点挂到结果中，l2指针后移，这时候l2的指针已经到末尾了，已经null了，则把l1的剩下的链表节点都挂到结果链表中，这样就得到了合并的链表。

用红色来表示l1的节点，则新链表为：1->1->2->3->4->4

时间复杂度为O(m+n).因为两个链表都要遍历一遍，m和n分别为链表的元素个数。

空间复杂度为O(1).

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
      if(list1==null)//边界情况
            return list2;
        if(list2==null)//边界情况
            return list1;
        ListNode resultNode=new ListNode(0);
        ListNode p=resultNode;//结果节点
        while(list1!=null&&list2!=null){//比较
            if(list1.val//l1节点的值小则把l1节点挂结果中
                p.next=list1;
                list1=list1.next;
            }else{
                p.next=list2;
                list2=list2.next;
            }
            p=p.next;
        }
        if(list1!=null){//其中一个链表指针遍历到末尾之后看哪个链表还没遍历完，若是l1没遍历完则把l1剩下的挂在结果中
            p.next=list1;
 
        }
        if(list2!=null){
            p.next=list2;//把l2没遍历完的挂在结果中
        }
        return resultNode.next;
    }
}

在IDEA上运行用的完整代码：

class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
        this.val=val;
    }
    public void add(int newval){
        ListNode newNode=new ListNode(newval);
        if(this.next==null){
            this.next=newNode;
        }
        else
            this.next.add(newval);
    }
    public void print(){
        System.out.print(this.val);
        if(this.next!=null)
        {
            System.out.print("->");
            this.next.print();
        }
    }
}
public class leetcode5 {
    /*循环+双指针解决*/
    static ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode resultNode=new ListNode(0);
        ListNode p=resultNode;
        while(l1!=null&&l2!=null){
            if(l1.val
                p.next=l1;
                l1=l1.next;
            }else{
                p.next=l2;
                l2=l2.next;
            }
            p=p.next;
        }
        if(l1!=null){
            p.next=l1;
 
        }
        if(l2!=null){
            p.next=l2;
        }
        return resultNode.next;
    }
    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.add(2);
        l1.add(4);
        l1.print();
        System.out.println();
        ListNode l2=new ListNode(1);
        l2.add(3);
        l2.add(4);
        l2.print();
        System.out.println();
        mergeTwoLists(l1,l2).print();
        System.out.println();
        System.out.println("hello list");
        /*
        1->2->4
        1->3->4
        1->1->2->3->4->4
        hello list 
        */
    }
}

---

解法2：递归

还是以示例一来演示，本来l1是1->2->4。l2是1->3->4。就是这两个链表要合并。然后如果把l2的1合并到l1之后就相当于是新l1：1->1->2->4和l2：3->4要合并。所以可以用递归来解决。

时间复杂度为O(m+n)

空间复杂度为O(m+n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        if(list1.val
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }
        list2.next=mergeTwoLists(list1,list2.next);
        return list2;
    }
}

在IDEA上运行用的完整代码：

class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
        this.val=val;
    }
    public void add(int newval){
        ListNode newNode=new ListNode(newval);
        if(this.next==null){
            this.next=newNode;
        }
        else
            this.next.add(newval);
    }
    public void print(){
        System.out.print(this.val);
        if(this.next!=null)
        {
            System.out.print("->");
            this.next.print();
        }
    }
}
public class leetcode5 {
    /*递归解决*/
    static ListNode mergeTwoLists2(ListNode l1,ListNode l2){
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        if(l1.val
            l1.next=mergeTwoLists2(l1.next,l2);
            return l1;
        }
        l2.next=mergeTwoLists2(l1,l2.next);
        System.out.print("->");
        System.out.print(l2.val);
        return l2;
    }
    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.add(2);
        l1.add(4);
        l1.print();
        System.out.println();
        ListNode l2=new ListNode(1);
        l2.add(3);
        l2.add(4);
        l2.print();
        System.out.println();
        System.out.println("hello list");
        System.out.println("下面的链表要倒着看");
        mergeTwoLists2(l1,l2);
        /*
        1->2->4
        1->3->4
        hello list
        下面的链表要倒着看
         ->4->4->3->2->1->1
         */
    }
}

---

加油加油^_^