题解 | #合并有序链表#（附带图解）

思路:

从题中给出的有效信息：

• 两个有序的链表
• 合并后新链表有序

故此两个有序的链表，合并两个链表可以使用 递归 和 双指针 的方式来解答

方法一：递归

具体做法：
如果l1节点值比l2小，将 l1的下一个节点 指向 l1.next 和 l2 合并后的头结点；l1节点值比l2小同理

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
          //当链表为空时返回
          if(l1 == null || l2 == null){
            return l1 != null ? l1 : l2;
        }
        //当链表l1小于l2时，l1的下一个节点 指向 l1.next 和 l2 合并后的头结点，反之亦然
        if(l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        } 
    }
}

复杂度分析：

• 时间复杂度：O(m+n) 需遍历l1,l2两个长度的链表
• 空间复杂度：O(m+n) 未申请额外的空间

方法二：双指针

具体做法：
定义一个临时的节点 list 来装载链表，节点 curr 指向 list，当 l1 和 l2都为空时 返回 list.next，指针l1的值比l2小 时，将 curr.next 指向 l2，然后将curr指向curr.next，反之同理；
具体过程如下图所示：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        ListNode list = new ListNode(0),curr = list;
        while(true){
            //l1,l2链表为空返回
            if(l1 == null && l2 == null){
                return list.next;
                //l1链表为空时，当前链表指向l2
            }else if(l1 == null && l2 != null){
                curr.next = l2;
                l2 = l2.next;
                //l2链表为空时，当前链表指向l1
            }else if(l2 == null && l1 != null){
                curr.next = l1;
                l1 = l1.next;
            }else {
                //l1与l2节点比较，将小的节点加入当前链表
                if(l1.val <= l2.val){
                    curr.next = l1;
                    l1 = l1.next;
                }else{
                    curr.next = l2;
                    l2 = l2.next;
                }
            }
            curr = curr.next;
        }
    }
}

复杂度分析：

• 时间复杂度：O(m+n) 需遍历l1,l2两个长度的链表
• 空间复杂度：O(1) 未申请额外的空间