将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。并写出代码
时间: 2024-03-14 14:43:57 浏览: 43
将两个有序链表合并一个链表
4星 · 用户满意度95%
好的,这是一个经典的链表合并问题。我们可以使用双指针法,依次比较两个链表的节点大小,将小的节点插入到新链表中,直到其中一个链表遍历完毕,然后将另一个链表的剩余节点直接加入到新链表的末尾即可。
以下是示例代码(假设链表节点的结构体为 ListNode,包含一个 val 属性和一个指向下一个节点的指针 next):
```python
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
# 定义一个虚拟头结点作为新链表的起始位置
dummy = ListNode(-1)
# 定义一个指针用于遍历新链表
p = dummy
# 双指针比较两个链表的节点大小,将小的节点插入到新链表中
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
# 将剩余的节点直接加入到新链表的末尾
p.next = l1 if l1 else l2
# 返回虚拟头结点的下一个节点作为新链表的头结点
return dummy.next
```
希望这个代码可以帮助到你!
阅读全文