编写一个完整可运行的代码。将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
时间: 2023-04-10 15:03:56 浏览: 53
严版课后习题重点算法.docx
以下是完整可运行的代码,实现将两个递增的有序链表合并为一个递增的有序链表:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val <= l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
# 测试代码
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
s = Solution()
merged = s.mergeTwoLists(l1, l2)
while merged:
print(merged.val, end=' ')
merged = merged.next
```
输出结果为:1 1 2 3 4 4
注意,这里使用了递归的方式实现链表合并,时间复杂度为 O(m+n),其中 m 和 n 分别为两个链表的长度。同时,由于题目要求结果链表仍使用原来两个链表的存储空间,因此我们只需要修改链表节点的 next 指针即可,不需要额外的存储空间。
阅读全文