将两个递增的有序链表合并为一个递增的有序链表
时间: 2023-10-18 20:05:39 浏览: 34
思路:
使用双指针法,分别指向两个链表的头结点,比较两个指针所指节点的大小,将较小的节点加入新链表,并将该链表的指针向后移动一位,直到一个链表遍历完毕,将剩余的节点接在新链表的尾部即可。
代码实现:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(-1)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1:
cur.next = l1
if l2:
cur.next = l2
return dummy.next
```
时间复杂度:$O(m+n)$,其中 $m$ 和 $n$ 分别为两个链表的长度。遍历一遍两个链表。空间复杂度:$O(1)$,只需常数个指针。