LeetCode每日一题： 合并两个有序链表

首先介绍自己的解法，写的有点复杂，大体思路就是先创建一个新链表，然后把两个链表中的val进行比较，把小的放入新链表中，直到有一个链表为空时结束循环，最后把剩下不为空的链表加到新链表后面。

代码：

class Solution {
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 != null && l2 == null){
        return l1;
    }else if(l1 == null && l2 != null){
        return l2;
    }else if(l1 == null && l2 == null){
        return l1;
    } //首先判断传进来的链表是否为空

    ListNode temp =  new ListNode();
    ListNode res = null;
    boolean flag = true;
    while(true){
       if(l1.val <= l2.val){
         temp.next = l1;  
          if(flag){
             res = temp.next;
             flag = false;
         }           
         if(l1.next != null){
         l1 = l1.next;    
         }else{
             l1 = l1.next;
             temp = temp.next;
             break;
         }               
       }else{
           temp.next = l2;  
            if(flag){
             res = temp.next;
             flag = false;
         }          
           if(l2.next != null){
           l2 = l2.next;
           }else{
               l2 = l2.next;
               temp = temp.next;
               break;
           }
       }        
       temp = temp.next;  
    }
   
    if(l1 == null){
        temp.next = l2;             
    }else if(l2 == null){
        temp.next = l1;             
    }
         return res;           
}
}

然后就是官方给出的解法，用的是递归（我当时咋就没想到呢，写了一大堆）

• 这道题可以使用递归实现，新链表也不需要构造新节点，我们下面列举递归三个要素
• 终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束
• 返回值：每一层调用都返回排序好的链表头
• 本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理
• O(m+n)，m 为 l1的长度，n 为 l2 的长度

代码：

class Solution {
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 == null) {
        return l2;
    }
    if(l2 == null) {
        return l1;
    }

    if(l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}
}