【复试上机】LeetCode-简单-007-Merge Two Sorted Lists
Merge Two Sorted Lists
前言：
这是归并排序的其中一个步骤，如果大家对数据结构知识点内容掌握比较到位的话，非常简单。
文字思想：
当两个单链表都不为空的时候，持续遍历两个单链表。将两个链表中更小的结点追加到新的单链表的尾巴上，并且对应的链表后移。
直到其中一个链表为空，再将不空的链表追加到新链表后面。
例子：
链表一：1, 2, 4,
链表二：1, 3, 4, 7, 8, 10,
新链表：
当前l1处理元素：1
当前l2处理元素：1
当前l1处理元素更小，尾插到新链表
l1后移一位
链表一：2, 4,
链表二：1, 3, 4, 7, 8, 10,
新链表：1,
当前l1处理元素：2
当前l2处理元素：1
当前l2处理元素更小，尾插到新链表
l2后移一位
链表一：2, 4,
链表二：3, 4, 7, 8, 10,
新链表：1, 1,
当前l1处理元素：2
当前l2处理元素：3
当前l1处理元素更小，尾插到新链表
l1后移一位
链表一：4,
链表二：3, 4, 7, 8, 10,
新链表：1, 1, 2,
当前l1处理元素：4
当前l2处理元素：3
当前l2处理元素更小，尾插到新链表
l2后移一位
链表一：4,
链表二：4, 7, 8, 10,
新链表：1, 1, 2, 3,
当前l1处理元素：4
当前l2处理元素：4
当前l1处理元素更小，尾插到新链表
l1后移一位
链表一：
链表二：4, 7, 8, 10,
新链表：1, 1, 2, 3, 4,
l1为空，现在直接将l2追加到新链表的尾巴
1, 1, 2, 3, 4, 4, 7, 8, 10,
代码：
复杂度：
时间复杂度：O(n+m)，因为在循环的时候每次处理一个元素。
空间复杂度：O(1)。
积累：
整体。
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20200908A09MMC00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
