两个有序链表的合并pta
时间: 2023-09-13 15:04:12 浏览: 36
题目描述:
给定两个升序链表,将其合并为一个升序链表并返回。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
解题思路:
我们可以使用递归的方法来实现两个有序链表的合并。具体做法是将两个链表的头部进行比较,将较小的节点作为合并后链表的头节点,然后递归地将较小节点的 next 指针指向其余节点的合并结果。
时间复杂度:O(n + m),其中 n 和 m 分别为两个链表的长度,因为每个节点只会被遍历一次。
空间复杂度:O(n + m),其中 n 和 m 分别为两个链表的长度,因为递归的深度等于两个链表的长度之和。
代码实现:
```python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
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
```
该算法的时间复杂度和空间复杂度都为 O(n + m)。