每天一题LeetCode【第18天】

T21. Merge Two Sorted Lists 【Easy】

题目

合并两个排好序的链表，返回新链表。需要通过将前两个链表的节点接在一起来完成新链表。

代码

代码参考 Top Solution，稍作注释

/**
 * 题目给出的ListNode类
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //若l1,l2是空的，则不用再合并，直接返回另一个就好
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        //通过相互比较，递归来得到最终结果
        if(l1.val < l2.val){
           //l1较小，所以接上l1以后得比较l1.next和l2那个小，接上l1
            l1.next = mergeTwoLists(l1.next, l2);
            //这次比较l1比较小，返回l1
            return l1;
        } else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

思路

这题之前有想过新建一个新链表l3然后l1,l2比大小一个个加入l3，然后返回l3，但是这要用到循环判断，代码也要多几行，Top Solution 里面的答案用了递归，感觉高大上一点。

这个算法就是递归嘛，没什么好说的（上面有注释），感觉这题给我的收获就是，我总是想不到用递归，但是递归真的好方便！要多记得用递归！

补充

分享一个我们从小就知道的递归~

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事就是：“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事就是：‘从前有座山，山里有座庙，庙里有个老和尚...'