输入两个链表,将两个链表升序合并为一个链表
时间: 2024-03-13 19:38:53 浏览: 30
以下是一个C语言的例子,用于将两个升序链表合并为一个新的升序链表并返回:
```c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
```
相关问题
两个升序链表合并为一个降序链表算法思想
要将两个升序链表合并为一个降序链表,可以使用递归的方式来实现。
首先,比较两个链表的头节点的值,将较小的节点作为新链表的头节点。然后,递归地将较小节点的下一个节点与另一个链表进行比较,将较小的节点连接到新链表的后面。重复这个步骤,直到其中一个链表为空。
当其中一个链表为空时,将另一个链表的剩余部分直接连接到新链表的后面,即可得到合并后的降序链表。
以下是一个示例的算法实现(假设链表节点的定义如下):
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_lists(l1, l2):
if not l1: # 如果l1为空,直接返回l2
return l2
if not l2: # 如果l2为空,直接返回l1
return l1
if l1.val < l2.val: # 比较头节点的值,选择较小的节点作为新链表的头节点
merged_head = ListNode(l1.val)
merged_head.next = merge_lists(l1.next, l2)
else:
merged_head = ListNode(l2.val)
merged_head.next = merge_lists(l1, l2.next)
return merged_head
```
这样,通过递归地合并两个升序链表,就可以得到一个降序链表。
将两个升序链表合并为一个新的升序链表并输出
以下是Python实现将两个升序链表合并为一个新的升序链表的方法:
```python
# 定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
# 如果其中一个链表为空,则直接返回另一个链表
if not l1:
return l2
if not l2:
return l1
# 定义一个新链表的头节点
dummy = ListNode(0)
# 定义一个指针指向新链表的头节点
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
# 将剩余的节点加入新链表中
if l1:
cur.next = l1
if l2:
cur.next = l2
# 返回新链表的头节点
return dummy.next
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)