如何合并两个递减单链表
时间: 2023-09-13 15:09:32 浏览: 42
合并两个递减单链表的方法如下:
1. 定义一个新的单链表,作为合并后的结果链表。
2. 分别从两个递减单链表的头节点开始遍历,比较两个节点的值的大小,将较大的节点插入到结果链表中,同时将指针向后移动一位。
3. 如果一个链表遍历完了,将另一个链表的所有剩余节点依次插入到结果链表中。
4. 返回结果链表。
具体实现可以参考下面的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_lists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val > l2.val:
cur.next, l1 = l1, l1.next
else:
cur.next, l2 = l2, l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
```
以上代码中,我们定义了一个 ListNode 类表示单链表的节点,merge_lists 函数用于合并两个递减单链表,返回合并后的结果链表。我们使用 dummy 节点作为结果链表的头节点,cur 节点用于遍历结果链表,同时也用于记录结果链表的尾节点。在遍历两个递减单链表的过程中,我们比较两个节点的值的大小,将较大的节点插入到结果链表中。当一个链表遍历完了,我们将另一个链表的所有剩余节点依次插入到结果链表中。最后返回结果链表即可。