本题要求实现一个合并两个有序链表的简单函数mergelists,函数参数list1和list2是用户传入的两个按data升序链接的链表的头指针;函数mergelists将两个链表合并成一个按data升序链接的链表,并返回结果链表的头指针。
时间: 2024-11-05 10:33:59 浏览: 14
题目要求编写一个名为`mergeLists`的函数,用于合并两个已排序的链表(`list1`和`list2`)。输入是这两个链表的头节点,输出是一个新的链表头节点,新链表包含了原两个链表中的元素,按升序排列。这个过程类似于归并排序中的合并两个有序数组。
下面是一个简单的Python实现思路:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeLists(list1, list2):
# 创建一个新的头节点,如果两个链表都为空,则返回None
dummy = ListNode(0)
current = dummy
while list1 and list2:
# 比较当前两个链表的头部元素,选择较小的那个添加到新链表
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# 如果其中一个链表还有剩余元素,将其添加到新链表尾部
current.next = list1 if list1 else list2
return dummy.next
```
阅读全文