第 25 题：合并排序的链表
传送门：AcWing：合并两个排序的链表，牛客网 online judge 地址。
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
样例：
输入：
1->3->5,2->4->5输出：
1->2->3->4->5->5
分析：同 LeetCode 第 21 题，传送门：21. 合并两个有序链表。这是一道经典的问题，可以使用“穿针引线”，也可以使用递归求解，个人觉得递归的代码比较简洁易懂。“穿针引线”则要画图。
思路1： 使用递归，编码简单。
Python 代码：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def merge(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 is None:
return l2
if l2 is None:
return l1
# 代码能走到这里说明 l1 和 l2 均非空
# 比较哪个小就行了
if l1.val < l2.val:
l1.next = self.merge(l1.next, l2)
return l1
# 走到这里 l1.val >= l2.val
l2.next = self.merge(l1, l2.next)
return l2
Java 代码：
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode Merge(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
} else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
}
思路2：穿针引线。
《剑指 Offer （第 2 版）》第 25 题：合并两个排序的链表-1
《剑指 Offer （第 2 版）》第 25 题：合并两个排序的链表-2
Python 代码：
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
# 穿针引线的写法，一定要画图才能写出来
# 比较麻烦，还是递归处理简单
class Solution(object):
def merge(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
# 引入头结点可以简化对问题的讨论
dummy_node = ListNode(-1)
cur_node = dummy_node
p1 = l1
p2 = l2
while p1 and p2:
# 两者都不为空，才须要比较
# 其中有一个为空的时候，把其中一个接到另一个尾巴就好了
if p1.val < p2.val:
# next 指针修改
cur_node.next = p1
# p1 后移
p1 = p1.next
else:
cur_node.next = p2
p2 = p2.next
cur_node = cur_node.next
# 跳出循环的时候，一定有：p1 为空或者 p2 为空
# 其中有一个为空的时候，把其中一个接到另一个尾巴就好了
if p1 is None: # 这一句写成 if not p1 也是可以的，不过不好理解
cur_node.next = p2
if not p2:
cur_node.next = p1
return dummy_node.next
