LEETCODE 21. Merge Two Sorted Lists 解题思路分析

题目大意：

合并两个有序链表

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=21

解题思路分析：

本题的合并方法很容易想到，从两个链表的头部开始比较，取出较小的一方，并将较小的一方的index移动到下一位，再继续比较，每次都保证取出较小的一方，最终合并结束之后一定是有小到大排序。

回到本题，具体来看下实现过程。由于思路很简单，实现方式应该很多，本题我们尝试使用递归来解决。我们从两个链表头部开始比较，将当前节点小的一方取出作为新链表的头，然后将小的一方的下一个节点和大的一方的节点传入递归子问题去找他们之间较小的一方，将子问题的解赋值到当前问题解的下一节点即可。

实现代码：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 如果链表1是空，返回链表2
    if(l1==null) return l2;
    // 如果链表2是空，返回链表1
    if(l2==null) return l1;
    // 如果链表1的值小于等于链表2当前值
    if(l1.val<=l2.val){
        // 取得链表1的下一个节点与链表2当前节点的最小值，赋值到链表1的下一个节点上
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }else{ // 如果链表2的值小于链表1当前值
        // 取得链表2的下一个节点与链表1当前节点的最小值，赋值到链表2的下一个节点上
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.

Memory Usage: 37.8 MB, less than 19.53% of Java online submissions for Merge Two Sorted Lists.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-21-merge-two-sorted-lists-解题思路分析/