系列文章目录
Python 算法学习：链表合成（升序）
文章目录
- 系列文章目录
- 一、算法需求
- 二、方法+源码
- 方法1：迭代
- 方法2：递归
- 方法3：函数sorted
- 方法4：双指针
- 方法5：heapq模块
- 总结
一、算法需求
给定两个升序排列的链表，采用多种方法，合并它们为一个新的升序链表。
二、方法+源码
方法1：迭代
- 这段代码首先创建了两个链表，然后调用merge_two_lists函数进行合并，并打印合并后的链表。输出应该是1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None，表示合并后的链表是升序的。
代码如下：
python">class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef merge_two_lists(l1, l2):# 创建一个虚拟头节点，便于处理链表的合并dummy = ListNode(0)current = dummywhile l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.next# 处理剩余节点current.next = l1 or l2return dummy.next# 创建链表 1 -> 2 -> 4
list1 = ListNode(1, ListNode(2, ListNode(4)))# 创建链表 1 -> 3 -> 4
list2 = ListNode(1, ListNode(3, ListNode(4)))# 合并链表
merged_list = merge_two_lists(list1, list2)# 打印合并后的链表
current = merged_list
while current:print(current.val, end=" -> ")current = current.next
print("None")
方法2：递归
-
这种方法的优点是代码简洁，直观地表达了合并链表的逻辑。然而，对于非常长的链表，递归可能会导致栈溢出。在实际应用中，迭代方法通常更受青睐，因为它避免了递归调用的开销。
-
在这个递归方法中：
首先检查l1或l2是否为空，如果为空，则直接返回另一个非空链表。
然后比较l1和l2当前节点的值，较小的那个节点会成为合并后链表的当前节点。
递归地调用merge_two_lists_recursive函数来合并剩下的链表部分，并将其链接到当前节点的next指针上。
最终返回合并后的链表的头节点。
代码如下：
python">class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef merge_two_lists_recursive(l1, l2):# 如果任意一个链表为空，直接返回另一个链表if not l1:return l2if not l2:return l1# 比较当前节点的值，递归合并较小的那个if l1.val < l2.val:l1.next = merge_two_lists_recursive(l1.next, l2)return l1else:l2.next = merge_two_lists_recursive(l1, l2.next)return l2# 测试递归方法
# 创建链表 1 -> 2 -> 4
list1 = ListNode(1, ListNode(2, ListNode(4)))# 创建链表 1 -> 3 -> 4
list2 = ListNode(1, ListNode(3, ListNode(4)))# 合并链表
merged_list = merge_two_lists_recursive(list1, list2)# 打印合并后的链表
current = merged_list
while current:print(current.val, end=" -> ")current = current.next
print("None")
方法3：函数sorted
-
这种方法利用了Python的排序功能，将两个链表的元素合并到一个列表中，然后对列表进行排序，最后将排序后的列表转换回链表。这种方法简单且易于理解，但可能在性能上不如迭代和递归方法，因为它涉及到额外的列表操作和排序时间。
-
在这个实现中：
listify 函数用于将链表转换为列表，通过遍历链表并收集每个节点的值。
to_linked_list 函数用于将列表转换回链表，通过创建新的链表节点并链接它们。
merge_two_lists_sorted 函数首先将两个链表转换为列表，然后将这两个列表合并并使用sorted函数进行排序，最后将排序后的列表转换回链表。 -
这种方法的优点是代码简洁，易于实现，特别是对于初学者来说。然而，它在处理非常大的数据集时可能不够高效，因为列表操作和排序过程可能会消耗较多时间和内存。对于需要高性能的场景，迭代或递归方法通常是更好的选择。
代码如下：
python">class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef merge_two_lists_sorted(l1, l2):# 将链表转换为列表def listify(head):result = []while head:result.append(head.val)head = head.nextreturn result# 将列表转换回链表def to_linked_list(lst):dummy = ListNode(0)current = dummyfor val in lst:current.next = ListNode(val)current = current.nextreturn dummy.next# 合并两个链表的元素并排序merged_list = sorted(listify(l1) + listify(l2))return to_linked_list(merged_list)# 测试排序方法
# 创建链表 1 -> 2 -> 4
list1 = ListNode(1, ListNode(2, ListNode(4)))# 创建链表 1 -> 3 -> 4
list2 = ListNode(1, ListNode(3, ListNode(4)))# 合并链表
merged_list = merge_two_lists_sorted(list1, list2)# 打印合并后的链表
current = merged_list
while current:print(current.val, end=" -> ")current = current.next
print("None")
方法4：双指针
-
这种方法与迭代方法类似，但是它使用两个指针分别遍历两个链表，并将节点插入到一个新的链表中，而不是直接链接到当前节点。这种方法可以减少链表节点的重新分配，因为它避免了在迭代过程中不断更新节点的next指针。
-
在这个实现中：
dummy 是一个虚拟头节点，用于简化链表的构建过程。
current 是一个指针，用于构建新的链表。
使用两个while循环分别遍历两个链表，每次比较当前节点的值，并将较小值的节点链接到新链表的末尾。
当其中一个链表遍历完成后，将另一个链表的剩余部分直接链接到新链表的末尾。
最后返回dummy.next，即合并后的链表的头节点。
代码如下：
python">class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef merge_two_lists_pointer(l1, l2):dummy = ListNode(0) # 创建一个虚拟头节点current = dummy # 使用current指针来构建新链表while l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.next# 处理剩余节点current.next = l1 if l1 is not None else l2return dummy.next # 返回合并后的链表头节点# 测试双指针方法
# 创建链表 1 -> 2 -> 4
list1 = ListNode(1, ListNode(2, ListNode(4)))# 创建链表 1 -> 3 -> 4
list2 = ListNode(1, ListNode(3, ListNode(4)))# 合并链表
merged_list = merge_two_lists_pointer(list1, list2)# 打印合并后的链表
current = merged_list
while current:print(current.val, end=" -> ")current = current.next
print("None")
方法5：heapq模块
-
该模块提供了一个基于堆的优先队列实现。我们可以将链表的元素添加到优先队列中，然后逐个取出最小的元素来构建新的链表。这种方法利用了堆的性质，可以高效地获取最小元素。
-
在这个实现中：
使用heapq模块的heappush和heappop函数来添加和移除元素。
每个元素是一个包含值、来源链表索引和节点本身的元组，这样可以在取出最小元素时知道下一步应该从哪个链表中取值。
使用一个虚拟头节点dummy和current指针来构建新的链表。
循环直到优先队列为空，每次循环中取出最小元素并将其链接到新链表中，然后检查并添加下一个节点到优先队列。 -
这种方法的优点是它可以高效地处理两个链表的合并，特别是当链表很长且元素数量不均衡时。然而，它需要额外的空间来存储优先队列，并且对于链表操作来说可能不如直接的链表操作直观。
代码如下：
python">import heapq
from collections import namedtuple# 定义一个包含值和来源链表索引的元组
ListNode = namedtuple('ListNode', ['val', 'node'])def merge_two_lists_heap(l1, l2):# 创建一个优先队列heap = []# 将两个链表的头节点添加到优先队列中if l1:heapq.heappush(heap, (l1.val, 0, l1))if l2:heapq.heappush(heap, (l2.val, 1, l2))dummy = ListNode(0) # 创建一个虚拟头节点current = dummy # 使用current指针来构建新链表# 从优先队列中逐个取出最小的元素while heap:val, list_idx, node = heapq.heappop(heap)current.next = nodecurrent = current.next# 如果当前节点的下一个节点不为空，则将其添加到优先队列中if node.next:heapq.heappush(heap, (node.next.val, list_idx, node.next))return dummy.next # 返回合并后的链表头节点# 测试heapq方法
# 创建链表 1 -> 2 -> 4
list1 = ListNode(1, None)
list1.node = ListNode(2, None)
list1.node.node = ListNode(4, None)# 创建链表 1 -> 3 -> 4
list2 = ListNode(1, None)
list2.node = ListNode(3, None)
list2.node = ListNode(4, None)# 合并链表
merged_list = merge_two_lists_heap(list1, list2)# 打印合并后的链表
current = merged_list
while current:print(current.val, end=" -> ")current = current.next
print("None")
总结
总而言之，每种方法都有其适用场景和优缺点。迭代和递归是最常用的方法，而双指针技术则提供了一种减少内存分配的方式。使用heapq模块的方法适合处理复杂的数据结构合并问题，而Python函数则提供了一种通用的解决方案。
