Python 实现反转、合并链表有啥用？

大家好，我是 V 哥。使用 Python 实现反转链表、合并链表在开辟中比较常见，我们先来看看各自的应用场景。先赞再看后评论，腰缠万贯财进门。

• 反转链表
  

比如，在处置惩罚时间序列数据时，有时需要将历史数据按照时间从近到远的顺序展示，如果数据是以链表形式存储的，通过反转链表可以高效地实现这一需求。再比如，判断一个链表是否为回文链表（即链表正序和逆序遍历的值相同）时，可以先反转链表的后半部分，然后与前半部分进行比较。再比如，在图像处置惩罚中，有时需要对图像进行水平或垂直翻转。如果图像数据以链表形式存储（例如，链表中的每个节点代表图像的一个像素），反转链表可以实现图像的水平翻转。

• 合并链表
  

比如，在大规模数据排序中，当数据量太大无法一次性加载到内存中时，可以采用多路归并排序算法。该算法将数据分成多个小块，分别排序后得到多个有序链表，然后通过合并这些有序链表得到最终的有序结果。合并链表是多路归并排序的核心操作之一。在数据库中，当实验多个查询操作并得到多个有序结果集时，需要将这些结果聚集并成一个有序的结果集。如果这些结果集以链表形式存储，合并链表可以高效地完成这个任务。在多媒体处置惩罚中，有时需要将多个音视频流合并成一个流。如果每个音视频流的数据以链表形式存储，合并链表可以实现音视频流的合并。
相识完反转链表和合并链表的应用场景，是不是跟 V 哥一样，这玩意儿还真挺有用的，那接下来，V 哥就具体介绍一个反转链表和合并链表。
反转链表

先看在 Python 中实现反转链表，我们可以使用迭代和递归两种方法。下面分别给出这两种方法的具体实现。
迭代方法

迭代方法的核心思想是遍历链表，在遍历过程中改变每个节点的指针方向，使其指向前一个节点。

1. # 定义链表节点类
2. class ListNode:
3.     def __init__(self, val=0, next=None):
4.         self.val = val
5.         self.next = next
7. def reverseList(head):
8.     # 初始化前一个节点为 None
9.     prev = None
10.     # 当前节点指向头节点
11.     curr = head
12.     while curr:
13.         # 保存当前节点的下一个节点
14.         next_node = curr.next
15.         # 将当前节点的指针指向前一个节点
16.         curr.next = prev
17.         # 前一个节点移动到当前节点
18.         prev = curr
19.         # 当前节点移动到下一个节点
20.         curr = next_node
21.     # 最终 prev 指向反转后的头节点
22.     return prev
24. # 辅助函数：将列表转换为链表
25. def list_to_linked_list(lst):
26.     dummy = ListNode(0)
27.     current = dummy
28.     for val in lst:
29.         current.next = ListNode(val)
30.         current = current.next
31.     return dummy.next
33. # 辅助函数：将链表转换为列表
34. def linked_list_to_list(head):
35.     result = []
36.     current = head
37.     while current:
38.         result.append(current.val)
39.         current = current.next
40.     return result
42. # 测试代码
43. input_list = [1, 2, 3, 4, 5]
44. head = list_to_linked_list(input_list)
45. reversed_head = reverseList(head)
46. output_list = linked_list_to_list(reversed_head)
47. print(output_list)  # 输出: [5, 4, 3, 2, 1]

复制代码

递归方法

递归方法的核心思想是先递归地反转当前节点之后的链表，然后将当前节点的指针指向前一个节点。

1. # 定义链表节点类
2. class ListNode:
3.     def __init__(self, val=0, next=None):
4.         self.val = val
5.         self.next = next
7. def reverseList(head):
8.     # 如果链表为空或只有一个节点，直接返回头节点
9.     if not head or not head.next:
10.         return head
11.     # 递归地反转当前节点之后的链表
12.     new_head = reverseList(head.next)
13.     # 将当前节点的下一个节点的指针指向当前节点
14.     head.next.next = head
15.     # 将当前节点的指针置为 None
16.     head.next = None
17.     return new_head
19. # 辅助函数：将列表转换为链表
20. def list_to_linked_list(lst):
21.     dummy = ListNode(0)
22.     current = dummy
23.     for val in lst:
24.         current.next = ListNode(val)
25.         current = current.next
26.     return dummy.next
28. # 辅助函数：将链表转换为列表
29. def linked_list_to_list(head):
30.     result = []
31.     current = head
32.     while current:
33.         result.append(current.val)
34.         current = current.next
35.     return result
37. # 测试代码
38. input_list = [1, 2, 3, 4, 5]
39. head = list_to_linked_list(input_list)
40. reversed_head = reverseList(head)
41. output_list = linked_list_to_list(reversed_head)
42. print(output_list)  # 输出: [5, 4, 3, 2, 1]

复制代码

以上两种方法都可以实现链表的反转，迭代方法的时间复杂度是 $O(n)$，空间复杂度是 $O(1)$；递归方法的时间复杂度也是 $O(n)$，但空间复杂度是 $O(n)$，主要是递归调用栈的开销。
使用 Python 实现链表的合并

在 Python 中实现链表的合并，常见的情况有合并两个有序链表和合并多个有序链表，下面分别介绍这两种情况的实现方法。
合并两个有序链表

合并两个有序链表的思绪是比较两个链表当前节点的值，将较小值的节点添加到结果链表中，然后移动相应链表的指针，直到其中一个链表遍历完，最后将另一个链表剩余的部分直接连接到结果链表的末尾。
[code]# 定义链表节点类class ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = nextdef mergeTwoLists(l1, l2):    # 创建一个虚拟头节点    dummy = ListNode(0)    # 当前节点指针，初始指向虚拟头节点    current = dummy    while l1 and l2:        if l1.val