21. Merge Two Sorted Lists

Tags

1. Linked List

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

题意：

将两个已排序的链表合并，并将其作为一个新的列表返回。新的列表应该是按顺序将第一个两个列表的节点拼接在一起的。

分析：

根据题意，可以知道给定的两个链表已经是排好序的(默认情况下都是按照升序排列，暂时假定)，然后需要将它们也按照这个规定拼接成一个新链表返回。如果是这样的话就很简单了，前面做过19题我们已经知道如何操作链表了(节点断开，节点连接)。所以思路就有了，我们比较每个列表中的第一个元素。然后将较小的一个添加到合并列表中。

思路：

根据上面的分析，采用递归法比较列表元素，思路如下：

1. 判断两个链表中的某个是否为null，如果为null则返回另外一个(其中一个null，另一个是否为null都无所谓，因为直接将它返回，所以无需再判断另一个)；
2. 判断两个链表的对应的节点value大小。如果l1.val小于l2.val，那么将l1当前节点作为根节点留下，将l1.next跟下一个比较后较小值的节点连接；否则就是将l2当前节点作为根节点留下，将l2.next跟下一个比较后较小值的节点连接，以此递归类推。

复杂度：

2n次递归调用，所以时间复杂度为O(n)

Js实现：

 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, 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(l2.next,l1);
        return l2;
    }
};