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