有序链表的合并
时间: 2023-07-10 09:19:45 浏览: 43
合并有序链表也可以使用双指针算法来解决。
具体实现方法如下:
1. 定义一个新的链表result,用于存放合并后的有序链表。
2. 定义两个指针p1和p2,分别指向两个有序链表的起始位置。
3. 依次比较两个链表中的节点大小,将较小的节点添加到result链表中,并将对应的指针向后移动一位。
4. 当其中一个链表的节点全部添加到result链表中后,将另一个链表中剩余的节点添加到result链表中。
5. 返回result链表。
下面是一个示例代码:
```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(l1, l2):
p1, p2 = l1, l2
dummy = ListNode(0)
cur = dummy
while p1 and p2:
if p1.val < p2.val:
cur.next = p1
p1 = p1.next
else:
cur.next = p2
p2 = p2.next
cur = cur.next
# 将剩余的节点添加到result链表中
cur.next = p1 if p1 else p2
return dummy.next
```
该算法的时间复杂度为O(m + n),其中m和n分别为两个有序链表的长度。