递增有序单链表L1、L2,不申请新结点,利用原表结点对两表进行合并,并使得合并后成为一个集合,合并后用L1的头结点作为头结点,删除多余的结点,删除L2的头结点。
时间: 2023-05-31 14:01:30 浏览: 68
算法流程如下:
1. 判断L1、L2是否为空,若有一个为空,则直接返回另一个链表。
2. 定义指针p、q分别指向L1、L2的头结点。
3. 如果L1的头结点的值比L2的头结点的值大,则交换p、q的指向,使得p指向较小的头结点。
4. 定义指针pre指向p,指针r指向p的下一个结点,指针s指向q的下一个结点。
5. 循环执行以下步骤,直到q为空:
(1) 如果r为空,则将pre的next指向q,返回L1。
(2) 如果r的值比q的值大,则将pre的next指向q,将q的next指向r,将q移动到s,将s移动到q的下一个结点。
(3) 否则,将pre、r分别移动到r的下一个结点,将q移动到s,将s移动到q的下一个结点。
6. 返回L1。
下面是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:
if not L1:
return L2
if not L2:
return L1
if L1.val > L2.val:
L1, L2 = L2, L1 # 交换L1、L2的指向
p, q = L1, L2
pre = p
while q:
if not p.next:
pre.next = q
break
if p.next.val > q.val:
pre.next = q
q.next, q = p.next, q.next
else:
pre, p = p, p.next
return L1
```
测试代码如下:
```python
# 构造测试数据
L1 = ListNode(1, ListNode(3, ListNode(5, ListNode(7))))
L2 = ListNode(2, ListNode(4, ListNode(6, ListNode(8))))
# 调用函数
L = merge_lists(L1, L2)
# 打印结果
while L:
print(L.val, end=' ')
L = L.next
# 输出:1 2 3 4 5 6 7 8
```
阅读全文
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.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)