题目
将两个升序链表合并为一个新的 升序 链表并返回
新链表是通过拼接给定的两个链表的所有节点组成的
规则示例
规则
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
示例1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例2:
输入:l1 = [], l2 = []
输出:[]
示例3:
输入:l1 = [], l2 = [0]
输出:[0]
解题分析一:迭代拼接
所谓迭代拼接,就是指将两个链表拼接为一个链表
每次比较链表的当前节点,较小的放入新的链表,当其中一个遍历完,则认为该新链表的后面部分都是另一个链表剩下的部分
相当于不停的去除两个链表当中较小的节点放入新链表当中
直到一个链表放完,后面部分就是另一个链表
我们以 L1 = [1,2,4] , L2 = [1,3,4] 为例子
第一次比较
第二次比较
第三次比较
第四次比较
第五次比较
最后一次比较
最后一次比较后我们只需要把新链表的下一个节点指向剩下的不为空的链表即可,这样可以保留剩下的节点关系,我们无需再进行比较判断
解题一:迭代拼接
解题分析二:递归
既然我们实现的MergeTwoLists函数是合并两个链表,每次寻找的目标都是值较小的那个链表节点,那么我们自然可以联想到使用MergeTwoLists函数来执行递归逻辑。
我们只需要找到递归结束的条件即可
根据题意我们知道,当任何一个链表当前节点为空时,后面部分可以直接使用剩下的另外一个链表的后半部分,那么这个可以作为一个结束条件
L1为空
L2为空
其它情况下,就得判断当前链表对应节点值的大小,如果找到其中较小的值的链表,那么可以使用自己的下一个节点后另一个链表节点进行比较
如果 L1.val <= L2.val
那么 L1.next = MergeTwoLists(L1.next, L2)
递归方法的关键就是要理解每次执行MergeTwoLists的目的就是要找到较小的那个节点来作为next,那么我们不停的递归,直到一个链表遍历结束,那么就可以得到一条完整的升序链表
解题二:
如果光靠想象理不清楚这里递归的逻辑
可以在纸上梳理一下逻辑走向,帮助自己理解
总结
这道题如果在笔试的时候遇到,建议大家使用递归的方式来进行制作。
这道题的考点就是考验大家对递归的灵活应用。
END