合并两个递增有序单链表为递减有序单链表
时间: 2023-09-09 12:13:05 浏览: 91
可以使用双指针来解决这个问题。假设有两个递增有序单链表L1和L2,我们要将它们合并为一个递减有序单链表L3。
首先创建一个空链表L3,然后比较L1和L2的头结点,将较小的结点插入到L3的头部。然后,将指向较小结点的指针向后移动一步。再次比较L1和L2的头结点,将较小的结点插入到L3的头部,指向较小结点的指针再向后移动一步。重复这个过程直到其中一个链表为空。
此时,将另一个非空链表的剩余结点插入到L3的头部即可。因为剩余的结点已经是有序的,所以只需要将它们插入到L3的头部即可。
以下是Python代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_lists(l1: ListNode, l2: ListNode) -> ListNode:
# 创建一个空链表L3
dummy = ListNode()
cur = dummy
# 比较L1和L2的头结点,将较小的结点插入到L3的头部
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
# 将剩余结点插入到L3的头部
if l1:
cur.next = l1
if l2:
cur.next = l2
# 反转L3
prev = None
cur = dummy.next
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)