LeetCode 二十一：合并两个有序链表【python】

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python

欢迎加入社区：码上找工作http://t.csdnimg.cn/Q59WX作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅

LeetCode解锁1000题: 打怪升级之旅https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化：企业实战案例https://blog.csdn.net/cciehl/category_12615648.html
备注说明：方便大家阅读，统一使用python，带必要注释，公众号数据分析螺丝钉一起打怪升级

引言

在算法面试中，链表问题是非常常见且基础的题型之一。题目“合并两个有序链表”要求将两个升序链表合并为一个新的升序链表并返回。这个问题考察了对链表数据结构的理解和操作能力，同时也是动态规划、递归思想的应用实例。

题目描述

给你两个升序排列的整数链表list1和list2，请你将两个链表合并，返回一个新的升序链表。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：list1 = [1,2,4], list2 = [1,3,4] 
输出：[1,1,2,3,4,4]

说明：

两个链表的节点数目范围是 [0, 50]。
-100 <= Node.val <= 100
list1 和 list2 均按非递减顺序排列

解题思路

方法一：迭代

迭代方法通过直观地比较两个链表的头节点，每次选取较小的节点添加到新链表的末尾，并移动指针，直至其中一个链表为空，最后将非空链表直接连接到新链表末尾。

代码示例

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:dummy = ListNode(-1)prev = dummywhile list1 and list2:if list1.val <= list2.val:prev.next = list1list1 = list1.nextelse:prev.next = list2list2 = list2.nextprev = prev.nextprev.next = list1 if list1 else list2return dummy.next

迭代法图解

使用指针prev遍历两个链表，每次选择较小的节点连接到prev，并移动指针，直至其中一个链表为空，然后将非空链表的剩余部分连接到合并链表的末尾。

初始化

dummy = Node(-1)作为新链表的哑节点。
prev = dummy作为当前节点的前一个节点。

迭代过程

比较list1和list2的头节点[1]和[2]，将1连接到prev，移动list1。
比较[3]和[2]，将2连接到prev，移动list2。
比较[3]和[4]，将3连接到prev，移动list1。
比较[5]和[4]，将4连接到prev，移动list2。
比较[5]和[6]，将5连接到prev，移动list1。
list1为空，将list2的剩余部分[6]连接到prev。

结果

通过迭代，最终得到的合并后的链表为[1, 2, 3, 4, 5, 6]。

方法二：递归

递归方法利用递归函数将问题分解为更小的子问题。如果list1的首元素小，那么它就应该是合并链表的首元素，其余元素由list1.next和list2合并得到；反之亦然。

代码示例

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:if not list1:return list2elif not list2:return list1elif list1.val < list2.val:list1.next = mergeTwoLists(list1.next, list2)return list1else:list2.next = mergeTwoLists(list1, list2.next)return list2