Skip to content

Latest commit

 

History

History
251 lines (201 loc) · 5.4 KB

21.merge-two-sorted-lists.md

File metadata and controls

251 lines (201 loc) · 5.4 KB

题目地址(21. 合并两个有序链表)

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

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

前置知识

公司

  • 阿里
  • 字节
  • 腾讯
  • amazon
  • apple
  • linkedin
  • microsoft

公司

  • 阿里、字节、腾讯

思路

本题可以使用递归来解，将两个链表头部较小的一个与剩下的元素合并，并返回排好序的链表头，当两条链表中的一条为空时终止递归。

关键点

  • 掌握链表数据结构
  • 考虑边界情况

代码

  • 语言支持：CPP, JS, Java, Python

CPP Code:

classSolution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == nullptr) { return l2; } elseif (l2 == nullptr) { return l1; } elseif (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } } };

JS Code:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */constmergeTwoLists=function(l1,l2){if(l1===null){returnl2;}if(l2===null){returnl1;}if(l1.val<l2.val){l1.next=mergeTwoLists(l1.next,l2);returnl1;}else{l2.next=mergeTwoLists(l1,l2.next);returnl2;}};

Java Code:

classSolution { publicListNodemergeTwoLists(ListNodel1, ListNodel2) { if (l1 == null) { returnl2; } elseif (l2 == null) { returnl1; } elseif (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); returnl1; } else { l2.next = mergeTwoLists(l1, l2.next); returnl2; } } }

Python Code:

classSolution: defmergeTwoLists(self, l1: ListNode, l2: ListNode) ->ListNode: ifnotl1: returnl2# 终止条件，直到两个链表都空ifnotl2: returnl1ifl1.val<=l2.val: # 递归调用l1.next=self.mergeTwoLists(l1.next,l2) returnl1else: l2.next=self.mergeTwoLists(l1,l2.next) returnl2

复杂度分析

M、N 是两条链表 l1、l2 的长度

  • 时间复杂度：$O(M+N)$
  • 空间复杂度：$O(M+N)$

扩展

  • 你可以使用迭代的方式求解么？

迭代的 CPP 代码如下：

classSolution { public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode head, *tail = &head; while (a && b) { if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; return head.next; } };

迭代的 JS 代码如下：

varmergeTwoLists=function(l1,l2){constprehead=newListNode(-1);letprev=prehead;while(l1!=null&&l2!=null){if(l1.val<=l2.val){prev.next=l1;l1=l1.next;}else{prev.next=l2;l2=l2.next;}prev=prev.next;}prev.next=l1===null ? l2 : l1;returnprehead.next;};

迭代的Java代码如下：

classSolution { publicListNodemergeTwoLists(ListNodel1, ListNodel2) { ListNodeprehead = newListNode(-1); ListNodeprev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev.next = l1 == null ? l2 : l1; returnprehead.next; } }

迭代的Python代码如下：

classSolution: defmergeTwoLists(self, l1: ListNode, l2: ListNode) ->ListNode: prehead=ListNode(-1) prev=preheadwhilel1andl2: ifl1.val<=l2.val: prev.next=l1l1=l1.nextelse: prev.next=l2l2=l2.nextprev=prev.next# 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev.next=l1ifl1isnotNoneelsel2returnprehead.next

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

close