将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
时间: 2023-10-18 12:08:56 浏览: 187
c++ 如何合并两个有序链表
5星 · 资源好评率100%
思路:
由于要使用原来两个链表的存储空间,因此可以直接将第二个链表中的节点插入到第一个链表中。具体地,遍历第二个链表中的每个节点,将其依次插入到第一个链表中的合适位置即可。
代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val <= l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
def reverseList(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
def merge(l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
l1 = reverseList(l1)
l2 = reverseList(l2)
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
if l1:
tail.next = l1
if l2:
tail.next = l2
return reverseList(dummy.next)
# 测试代码
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
merge(l1, l2)
```
复杂度分析:
- 时间复杂度:$O(m+n)$,其中 $m$ 和 $n$ 分别为两个链表的长度,需要遍历两个链表。
- 空间复杂度:$O(1)$,只需要常数的额外空间。
阅读全文