采用单链表归并有序表的代码
时间: 2024-09-23 15:11:58 浏览: 23
当你有一个包含多个已排序链表的列表,并希望将它们合并成一个新的有序链表时,可以使用归并排序的思想。这里提供一种简单的Python示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(lists):
# 创建一个空节点作为结果链表的头
dummy = ListNode(0)
current = dummy
while lists:
# 找到各链表当前最小值的节点
min_node = lists[0]
for i in range(1, len(lists)):
if lists[i].val < min_node.val:
min_node = lists[i]
# 将找到的最小值节点添加到结果链表中
current.next = min_node
min_node = min_node.next
# 移除已经处理过的链表头部节点
lists.remove(min_node)
# 如果还有其他链表,则继续循环
if lists:
current = current.next
return dummy.next # 返回结果链表的头
# 示例:
list1 = ListNode(1, ListNode(2, ListNode(4)))
list2 = ListNode(1, ListNode(3, ListNode(5)))
# ... 其他链表...
merged_list = merge_sorted_lists([list1, list2]) # 合并后的链表
```
这个代码首先创建了一个虚拟头节点`dummy`,然后遍历各个链表,取出当前最小的元素加入到新链表中,直到所有链表都被处理完。这样就得到了一个有序的合并后的链表。