已知递减有序的两个单链表A和B,写算法将A、B归并成一个递减有序的单链表C。
时间: 2024-11-29 16:18:36 浏览: 41
为了合并两个递减有序的单链表A和B,我们可以创建一个新的单链表C,然后按照从大到小的顺序链接节点。以下是步骤:
1. 初始化三个指针:`p1`指向A的头结点,`p2`指向B的头结点,`pC`初始化为空。
2. 当`p1`或`p2`不为空时,执行循环:
- 比较`p1`和`p2`所指节点的值,选择较大的节点(如果它们都未排序则取较小的)作为新链表C的下一个节点,并移动对应的指针(例如,`pC->next = p1; p1 = p1->next`)。
- 如果遍历完其中一个链表而另一个链表还有剩余节点,则把剩下的链表直接接到C的尾部。
3. 当两个链表都遍历完毕,`pC->next`会指向剩余的那个链表的头结点,如果没有剩余,说明已经完成合并。
以下是伪代码形式的实现:
```python
def merge_sorted_lists(A, B):
if not A or not B:
return A if not B else B
elif A->value > B->value:
C->next = A
A = A->next
else:
C->next = B
B = B->next
C = C->next
while A and B:
if A->value > B->value:
C->next = A
A = A->next
else:
C->next = B
B = B->next
C = C->next
# 如果B还有剩余,直接连接
if B:
C->next = B
# 否则,如果A有剩余,连接A
else:
C->next = A
return C
```
阅读全文
相关推荐


















