设计一个算法MergeList,将两个递增的有序链表合并为一个递增的有序链表。 要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间,合并时去除重复的数据。
时间: 2024-09-20 21:17:34 浏览: 48
设计这个算法MergeList,我们可以使用迭代的方式解决,步骤如下:
1. 初始化两个指针,分别指向第一个链表的头节点p1和第二个链表的头节点p2。
2. 创建一个新的链表head,初始化为None,作为合并后的链表头部。
3. 定义一个新的指针current,初始值设为head。
4. 当p1和p2都非空时,比较它们的值:
- 如果p1的值小于或等于p2的值,将p1的值插入到当前链表current之后,并移动p1到下一个节点。
- 否则,将p2的值插入到当前链表current之后,并移动p2到下一个节点。
5. 每次插入节点后,都要检查新插入的节点是否已经存在于新的链表中。如果存在,跳过该节点;如果不存在,则更新current指向新插入的节点。
6. 当其中一个链表遍历完后,将另一个链表剩余部分依次添加到新链表中。
以下是Python伪代码示例:
```python
def merge_sorted_lists(p1, p2):
head = None
current = head
while p1 is not None and p2 is not None:
if p1.val <= p2.val:
# 插入并检查是否重复
if current.next is None or p1.val != current.next.val:
current.next = p1
p1 = p1.next
else:
p1 = p1.next
else:
if current.next is None or p2.val != current.next.val:
current.next = p2
p2 = p2.next
else:
p2 = p2.next
# 将剩余链表添加到新链表
if p1 is not None:
current.next = p1
elif p2 is not None:
current.next = p2
return head
```
阅读全文