2、现有两个递减的有序链表(带头结点的单链表),分别为La和Lb,需要合并成一个新的链表Lc,请你完成链表合并函数。
时间: 2023-05-30 16:06:19 浏览: 151
将两个有序链表合并一个链表
4星 · 用户满意度95%
算法思路:
1. 定义一个新的链表头结点Lc,初始化为空。
2. 分别定义两个指针pa和pb,分别指向La和Lb的头结点。
3. 比较pa和pb指向的节点的值的大小,将较小的节点插入到Lc链表的末尾,并将其指针后移。
4. 循环执行步骤3,直到La或Lb中的一个链表遍历完毕。
5. 将未遍历完的链表中的所有节点插入到Lc链表的末尾。
6. 返回Lc链表的头结点。
Python 代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(La: ListNode, Lb: ListNode) -> ListNode:
Lc = ListNode() # 定义一个新的链表头结点Lc,初始化为空
pc = Lc # 定义一个指针pc,指向Lc的头结点
pa, pb = La.next, Lb.next # 分别定义两个指针pa和pb,指向La和Lb的头结点
while pa and pb: # 当La和Lb都不为空时
if pa.val < pb.val: # 如果La中的节点值小于Lb中的节点值
pc.next = pa # 将pa指向的节点插入到Lc链表的末尾
pa = pa.next # 将pa指针后移
else: # 如果Lb中的节点值小于或等于La中的节点值
pc.next = pb # 将pb指向的节点插入到Lc链表的末尾
pb = pb.next # 将pb指针后移
pc = pc.next # 将pc指针后移
if pa: # 如果La链表还有未遍历的节点
pc.next = pa # 将所有未遍历的节点插入到Lc链表的末尾
if pb: # 如果Lb链表还有未遍历的节点
pc.next = pb # 将所有未遍历的节点插入到Lc链表的末尾
return Lc # 返回Lc链表的头结点
```
阅读全文