【LeetCode每日一题】21. Merge Two Sort

题目描述

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

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

通过合并两个有序链表生成一个新的有序链表。新链表由这两个链表的节点构成。

分析&解答

链表主要由节点构成，节点之间通过指针链接。两个有序链表的合并的核心在于指针的处理，怎么把两个链表的节点通过指针链接起来，形成新的有序链表。

因为，生成的新链表也是有序的，所以，我们依次比较两个链表的节点，把值小的节点先链接到结果链表中，直到两个链表结束。

具体思路为：

• 我们先考虑corner case，如果两个链表中存在空链表，则返回其中的非空链表（当两个链表都是空链表时，返回任意一个）；
• 正常情况，即两个链表均为不为空，使用两个指针分别指向两个链表，然后依次比较两个链表的节点，把值小的节点链接到结果链表中，然后更新节点指针；当指向两个链表的指针为空时，结束循环；最后，把其中的非空指针链接到结果链表中。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1 || !l2) return l1 ? l1 : l2;
        
        ListNode *first = new ListNode(-1), *node = first;
        
        while (l1 && l2){
            if (l1->val < l2->val){
                node->next = l1;
                l1 = l1->next;
            }
            else{
                node->next = l2;
                l2 = l2->next;
            }
            node = node->next;
        }
        if (l1) node->next = l1;
        if (l2) node->next = l2;
        
        return first->next;
    }
};

Python代码思路和cpp一样：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l2 if not l1 else l1
        first = node = ListNode(-1)
        
        while l1 and l2:
            if l1.val < l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
            
        if l1:
            node.next = l1
        if l2:
            node.next = l2
        
        return first.next

---

欢迎关注公众号，一起学习