【LeetCode每日一题】21. Merge Two Sorted Lists
【LeetCode每日一题】21. Merge Two Sorted Lists
公众号-不为谁写的歌
发布于 2020-07-23 18:16:56
发布于 2020-07-23 18:16:56
文章被收录于专栏：桃花源记
题目描述
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本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/07/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
