编写代码 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表向存储空间,不另外占用其他的存储空间。表中不允许有重复的数据
时间: 2024-09-22 10:07:08 浏览: 47
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
当需要将两个递增的有序链表合并成一个新的递增有序链表,并且要求原链表的空间不变,我们可以采用一种常见的迭代或递归方法。这里提供一个简单的迭代解决方案:
首先,创建一个新的头节点`dummy`,并将其next指针设为None,用于模拟合并后的链表。然后,遍历两个链表的头部,每次比较两个链表当前节点的值,选择较小的那个作为新链表的下一个节点,同时更新当前节点指向剩余的链表。
以下是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) # 创建虚拟头节点
current = dummy # 初始化合并后链表的指针
while l1 and l2: # 当两个链表都不为空
if l1.val < l2.val: # 如果l1的值小
current.next = l1 # 更新新链表的下一个节点
l1 = l1.next # 移动l1的指针
else: # 否则,l2的值小
current.next = l2 # 更新新链表的下一个节点
l2 = l2.next # 移动l2的指针
current = current.next # 指针向前移动
# 添加剩下的链表到最后
if l1 is not None:
current.next = l1
elif l2 is not None:
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)
```
阅读全文