用Python设计算法,将两个递增的有序链表合并为一个递增的有序链表。结果要求链表扔使用原来的两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
时间: 2024-11-09 11:17:16 浏览: 11
在Python中,可以使用双指针法来合并两个递增的有序链表。这里是一个简单的步骤描述:
1. 定义一个新的头节点 `dummy` 和两个指针 `p1` 和 `p2`,分别指向第一个链表和第二个链表的头部。
2. 初始化 `p1` 和 `p2` 为各自的头节点。
3. 创建一个循环,直到其中一个指针为空:
a. 比较 `p1` 和 `p2` 的值,选择较小的那个节点(如果它们都非空)将其添加到新链表中,并移动该指针到下一个节点。
b. 如果只有一个节点剩余,则直接将另一个链表的剩余部分接上新链表。
4. 将 `dummy.next` 设置为合并后的链表的头部。
以下是这个算法的Python实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(l1, l2):
dummy = ListNode(0) # 创建虚拟头节点
p = dummy # 新链表头指针
while l1 and l2: # 只要l1和l2都有元素
if l1.val <= l2.val: # 将较小的节点添加到新链表
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next # 移动新链表头指针
# 添加剩余的链表,如果有
if l1 is not None:
p.next = l1
elif l2 is not None:
p.next = l2
return dummy.next # 返回合并后的链表头部
```
阅读全文