21. Merge Two Sorted Lists

置顶

Created At : 2021-04-07 23:57

Count:1.1k Views 👀 :

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

**Input:** list1 = [1,2,4], list2 = [1,3,4]
**Output:** [1,1,2,3,4,4]

Example 2:

**Input:** list1 = [], list2 = []
**Output:** []

Example 3:

**Input:** list1 = [], list2 = [0]
**Output:** [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

这道混合插入有序链表和博主之前那篇混合插入有序数组非常的相似 Merge Sorted Array，仅仅是数据结构由数组换成了链表而已，代码写起来反而更简洁。具体思想就是新建一个链表，然后比较两个链表中的元素值，把较小的那个链到新链表中，由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素，则直接另一个未完成的链表直接链入新链表的末尾。代码如下：

C++ 解法一：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            } else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2;
        return dummy->next;
    }
};

Java 解法一：

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1), cur = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

下面来看递归的写法，当某个链表为空了，就返回另一个。然后核心还是比较当前两个节点值大小，如果 l1 的小，那么对于 l1 的下一个节点和 l2 调用递归函数，将返回值赋值给 l1.next，然后返回 l1；否则就对于 l2 的下一个节点和 l1 调用递归函数，将返回值赋值给 l2.next，然后返回 l2，参见代码如下：

C++ 解法二：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

Java 解法二：

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

下面这种递归的写法去掉了 if 从句，看起来更加简洁一些，但是思路并没有什么不同：

C++ 解法三：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
        ListNode *head = list1->val < list2->val ? list1 : list2;
        ListNode *nonhead = list1->val < list2->val ? list2 : list1;
        head->next = mergeTwoLists(head->next, nonhead);
        return head;
    }
};

Java 解法三：

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode head = (list1.val < list2.val) ? list1 : list2;
        ListNode nonhead = (list1.val < list2.val) ? list2 : list1;
        head.next = mergeTwoLists(head.next, nonhead);
        return head;
    }
}

我们还可以三行搞定，简直丧心病狂有木有！

C++ 解法四：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1 || (list2 && list1->val > list2->val)) swap(list1, list2);
        if (list1) list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
};

Java 解法四：

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || (list2 != null && list1.val > list2.val)) {
            ListNode t = list1; list1 = list2; list2 = t;
        }
        if (list1 != null) list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }
}

Github 同步地址：

https://github.com/grandyang/leetcode/issues/21

类似题目：

Merge Sorted Array

Merge k Sorted Lists

Sort List

Shortest Word Distance II

参考资料：

https://leetcode.com/problems/merge-two-sorted-lists/

https://leetcode.com/problems/merge-two-sorted-lists/discuss/9714/14-line-clean-C%2B%2B-Solution

https://leetcode.com/problems/merge-two-sorted-lists/discuss/9814/3-lines-C%2B%2B-(12ms)-and-C-(4ms)

https://leetcode.com/problems/merge-two-sorted-lists/discuss/9715/Java-1-ms-4-lines-codes-using-recursion