新建两个链表AList和BList并完成如下操作: AList : 7 6 5 2 1 BList : 9 7 5 3 2 (1)将两个链表按从高到低的顺序合并为一个链表
时间: 2024-10-15 11:25:08 浏览: 24
为了按照从高到低的顺序合并两个链表AList和BList,我们可以创建一个新的链表CList,并采用逐节点比较的方式来构建。以下是步骤:
1. 创建一个新链表CList,头节点初始化为空。
2. 比较AList和BList的当前节点值,选择较大的一个添加到CList中,然后移动该链表的指针。
3. 如果其中一个链表已经遍历完,直接将另一个链表剩余的部分连接到CList的末尾。
下面是具体的Python代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_lists(headA, headB):
dummy = ListNode(0) # 创建虚拟头节点
current = dummy # 当前节点指向dummy
while headA and headB:
if headA.val > headB.val:
current.next = headA
headA = headA.next
else:
current.next = headB
headB = headB.next
current = current.next
# 将剩余未遍历完的链表连接到CList
if headA:
current.next = headA
elif headB:
current.next = headB
return dummy.next # 返回合并后的链表头节点
# 初始化链表
AList = [7, 6, 5, 2, 1]
headA = ListNode(AList[0])
for num in AList[1:]:
headA.next = ListNode(num)
headA = headA.next
BList = [9, 7, 5, 3, 2]
headB = ListNode(BList[0])
for num in BList[1:]:
headB.next = ListNode(num)
headB = headB.next
# 合并链表
merged_list = merge_lists(headA, headB)
# 打印合并后的链表
current = merged_list
while current:
print(current.val, end=' ')
current = current.next
```
阅读全文