python请编写算法将这两个单链表归并为一个按元素值升序排列的单链表。
时间: 2024-06-10 14:05:38 浏览: 85
可以使用归并排序的思路实现两个单链表的归并操作。
首先,定义一个新的单链表节点用于存储归并后的结果。
然后,利用双指针分别遍历两个单链表,将元素值小的节点添加到新的单链表节点中,并移动相应的指针。
最后,判断哪个链表还有剩余未遍历的节点,将其直接添加到新的单链表节点的末尾即可。
下面是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(-1)
p = dummy
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
p.next = l1 if l1 else l2
return dummy.next
```
其中,`l1`和`l2`分别为要归并的两个单链表的头节点,`dummy`为新的单链表的哨兵节点。
接下来,调用上述函数即可完成对两个单链表的归并操作。例如:
```python
head1 = ListNode(1)
head1.next = ListNode(3)
head1.next.next = ListNode(5)
head2 = ListNode(2)
head2.next = ListNode(4)
head2.next.next = ListNode(6)
merged = mergeTwoLists(head1, head2)
while merged:
print(merged.val, end=" ")
merged = merged.next
```
最终输出结果为:`1 2 3 4 5 6`。
阅读全文