[已解决]设计两个有序单链表的合并排序算法。

15278363968

设计两个有序单链表的合并排序算法。

最佳答案

月排行榜 / 总排行榜

陶远航

2023-7-9 19:09:11

要设计两个有序单链表的合并排序算法，可以采用迭代的方法来实现。下面是一个示例算法：

1. class ListNode:
2.     def __init__(self, val=0, next=None):
3.         self.val = val
4.         self.next = next
6. def mergeTwoLists(l1, l2):
7.     dummy = ListNode(0)
8.     current = dummy
10.     while l1 and l2:
11.         if l1.val < l2.val:
12.             current.next = l1
13.             l1 = l1.next
14.         else:
15.             current.next = l2
16.             l2 = l2.next
17.         current = current.next
19.     if l1:
20.         current.next = l1
21.     if l2:
22.         current.next = l2
24.     return dummy.next

复制代码

在这个算法中，我们使用了一个虚拟节点 dummy 和一个当前指针 current 来构建新的有序链表。然后我们依次比较两个链表的节点值，将较小的节点添加到新链表中，并将指针向后移动。

最后，如果其中一个链表遍历完了，我们将另一个链表剩余的部分直接添加到新链表的末尾。

您可以调用这个函数来合并两个有序单链表，如下所示：

1. # 创建链表1
2. l1 = ListNode(1)
3. l1.next = ListNode(3)
4. l1.next.next = ListNode(5)
6. # 创建链表2
7. l2 = ListNode(2)
8. l2.next = ListNode(4)
9. l2.next.next = ListNode(6)
11. # 合并排序
12. merged = mergeTwoLists(l1, l2)
14. # 打印合并后的链表
15. while merged:
16.     print(merged.val)
17.     merged = merged.next

复制代码

这将输出合并后的有序链表的节点值。

希望对您有帮助！如果您有更多问题，请随时提问。

跳转到最佳答案楼层