将两个非递减的有序链表合并为一个非递增的线性表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
时间: 2024-03-25 19:15:32 浏览: 13
算法步骤:
1. 比较两个链表头结点的值,将值较大的节点作为新链表的头结点。
2. 将较小的节点插入到新链表中,插入位置为新链表中值等于或小于该节点值的节点后面。
3. 重复执行步骤2,直到某一个链表为空。
4. 将剩余链表的所有节点插入到新链表中。
代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeLists(l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val >= l2.val:
head = l1
l1 = l1.next
else:
head = l2
l2 = l2.next
tail = head
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 head
def reverseList(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
head = mergeLists(l1, l2)
return reverseList(head)
```
时间复杂度:$O(m+n)$,其中 $m$ 和 $n$ 分别为两个链表的长度。
空间复杂度:$O(1)$,只使用常数个变量。