用Python代码设计两个有序单链表的合并排序算法,并给出主代码
时间: 2024-03-02 20:53:34 浏览: 64
python 实现合并两个有序链表
下面是用Python代码实现两个有序单链表合并排序的算法,包括链表节点定义、合并排序函数和主函数:
```python
# 链表节点定义
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 合并排序函数
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1:
cur.next = l1
else:
cur.next = l2
return dummy.next
# 主函数
if __name__ == '__main__':
l1 = ListNode(1, ListNode(3, ListNode(5)))
l2 = ListNode(2, ListNode(4, ListNode(6)))
l = mergeTwoLists(l1, l2)
while l:
print(l.val, end=' ')
l = l.next
```
在主函数中,我们创建了两个有序单链表l1和l2,并将它们传入合并排序函数mergeTwoLists中进行合并排序。最后,我们遍历合并后的单链表l并输出每个节点的值。
阅读全文