将两个递增的有序链表合并为一个递增的有序链表。要求结果链仍使用原来两个链表的存储空间,不占用其他空间,表中不能有重复数据。给我代码
时间: 2024-10-12 13:10:41 浏览: 25
将两个递增的有序链表合并成一个新的有序链表,可以采用双指针法。首先创建一个新的头结点,并让两个链表的头节点依次与新链表的头节点进行比较,将较小的节点添加到新链表并更新当前节点,直到其中一个链表遍历完。然后将另一个链表剩余部分接到新链表的尾部。
以下是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 is not None and l2 is not None: # 只要两个链表都非空
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
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)
```
在这个例子中,`merge_sorted_lists`函数接受两个链表的头节点作为输入,返回合并后的有序链表头节点。注意,这个实现保留了原链表的空间结构,没有额外创建新的节点数组。
阅读全文