将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。算法设计代码
时间: 2024-10-10 08:07:03 浏览: 32
将两个递增的有序链表合并成一个有序链表,可以采用迭代或递归的方式实现,关键在于比较节点值并保持链表的递增顺序。这里提供一种迭代的解决方案:
```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)
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
# 如果其中一个链表还有剩余元素,则追加到新链表末尾
if l1:
current.next = l1
elif l2:
current.next = l2
return dummy.next # 返回合并后的链表头节点
# 示例
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
merged_list = merge_sorted_lists(l1, l2)
```
在这个算法中,我们创建了一个虚拟头节点 `dummy` 和一个指向当前节点的指针 `current`。遍历两个输入链表,每次比较当前节点的值,选择较小的那个添加到新的链表,并更新当前节点。最后返回 `dummy.next` 即得到合并后的有序链表。
阅读全文