请设计算法,将两个递增有序单链表la和lb合并为一个递减有序表(写出算法核心语句即可)
时间: 2024-10-14 22:08:04 浏览: 35
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
设计这样的算法可以采用迭代或递归的方式。这里给出一种迭代的核心思路:
```python
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(la, lb):
# 创建新的头结点
dummy = ListNode(0)
tail = dummy
# 遍历链表,每次从较大的元素开始取
while la and lb:
if la.val > lb.val:
tail.next = lb
lb = lb.next
else:
tail.next = la
la = la.next
tail = tail.next
# 将剩余未遍历完的部分追加到结果链表末尾
if la:
tail.next = la
elif lb:
tail.next = lb
return dummy.next
```
这个算法的核心步骤是在循环中比较`la`和`lb`的当前元素值,然后将较大元素的节点链接到结果链表的尾部,并更新指向下一个节点的指针。最后返回合并后的链表头。
阅读全文