- 一、前言
- 二、合并两个有序链表
- 1、题意
- 2、示例
- 3、题解
- 方法一递归算法
- 思路分析
- 代码解析
- 方法二迭代算法
- 思路分析
- 代码解析
- 总结
最近几天有点忙，没来得及更新我的力扣刷题笔记，今天1024跑来记录一下，嘻嘻嘻來
二、合并两个有序链表 1、题意将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
2、示例3、题解 方法一递归算法 思路分析示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
我们可以通过比较两个链表头节点的值，得到头节点较小的链表节点，然后再将它与剩下元素合并后的有序链表（迭代mergeTwoLists操作）连接在一起。
合并两个有序链表的结果有如下四种：
①若链表l1为空，链表l2不为空，则返回的结果为链表l2；
②若链表l2为空，链表l1不为空，则返回的结果为链表l1；
③若链表l1和l2均为空，则返回任意一个链表皆可；
④若链表l1和l2均不为空，则我们可以递归两个链表的mergeTwoLists操作，递归方程如下所示：
当l1[0]
C语言:
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if(l1 == NULL)
return l2;
else if(l2 == NULL)
return l1;
else if(l1->val < l2->val)
{
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else
{
l2->next = mergeTwoLists(l2->next, l1);
return l2;
}
}
python:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1:
return l2
elif not l2:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
java:
class Solution
{
//采用递归的思想
public ListNode mergeTwoLists(ListNode l1, ListNode l2)
{
if(l1 == null)
return l2;
else if(l2 == null)
return l1;
else if(l1.val < l2.val)
{
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else
{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
方法二迭代算法
思路分析
当l1和l2都不为空链表的时候，通过判断两个链表l1和l2的头节点的值的大小，找到值较小的节点并将该节点添加到结果中，当一个节点被添加到结果中去后，我们就将对应链表的节点往后移一位。具体的算法实现可以通过设定一个哨兵节点prehead，最终我们需要返回的结果值就是prehead->next（也就相当于我们把后期合并好的有序链表看作了一个整体，也就是prehead->next）。另外，我们还需要维护一个prev指针，初始化时我们将prehead赋给prev，后面通过
代码解析C语言：
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode *prehead, *prev;
prehead = (struct ListNode*)malloc(sizeof(struct ListNode));
prehead->val = -1;
prev = prehead;
while(l1 && l2)
{
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 ? l1 : l2;
return prehead->next;
}
python:
class Solution(Object): def mergeTwoLists(self, l1, l2): prehead = ListNode(-1) prev = prehead while l1 and l2: if l1.val <= l2.val: prev.next = l1 l1 =l1.next else: prev.next = l2 l2 = l2.next prev = prev.next prev.next = l1 if l1 else l2 return prehead.next
java:
class Solution{
public ListNode mergeTwoLists(ListNode l1, ListNode l2)
{
ListNode prehead = new ListNode(-1);
ListNode prev = 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;
return prehead.next;
}
}
总结
1、python定义的函数中的self代表的是类的实例，类似于java语言中的this，所以如果我们把self换成this，结果也一样，但是在Python中最好用约定俗成的self。
2、迭代法的妙处就在于它构造了一个prehead哨兵节点，后面的合并链表排序交给prev来完成，最终返回的结果就是prehead->next，非常方便。这样就避免了再去创建一个新的链表，把排序好的节点再依次放进去的复杂操作。
3、这道题之所以能用递归算法来求解，是因为它能把本来求解两个有序链表合并的复杂问题分解为：先找出两个链表分别的头节点最小的值，再让剩下的两个链表完成和前面同样的操作（也就是两个有序链表合并的操作）。
