怎么合并两个有序链表
时间: 2024-01-24 16:12:58 浏览: 34
要合并两个有序链表,可以使用递归或迭代的方法。以下是迭代的方法:
假设有两个有序链表l1和l2,我们可以创建一个新的链表result,然后比较l1和l2的头节点,将较小的节点加入result中,直到其中一个链表为空。最后,将另一个非空链表的剩余部分加入result中。
以下是C++代码实现:
```c++
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* result = new ListNode(0);
ListNode* cur = result;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1 != nullptr) {
cur->next = l1;
} else {
cur->next = l2;
}
return result->next;
}
```
相关问题
合并两个有序链表
好的,这是一个经典的问题。假设我们要合并的两个有序链表分别为 l1 和 l2,那么我们可以按照以下步骤进行合并:
1. 定义一个新的链表 dummy,作为合并后链表的头结点。
2. 定义两个指针 p1 和 p2,分别指向 l1 和 l2 的头结点。
3. 定义一个指针 cur,初始时指向 dummy。
4. 比较 p1 和 p2 指向的节点的值,将较小的节点接到 cur 的后面,并将对应的指针后移一位。
5. 重复步骤 4,直到 p1 或 p2 为空。
6. 将剩余的节点接到 cur 的后面。
7. 返回 dummy 的下一个节点,即合并后的有序链表的头结点。
下面是一份示意代码,供您参考:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
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
cur.next = l1 if l1 else l2
return dummy.next
```
以上就是合并两个有序链表的方法,希望能对您有所帮助。
合并两个有序链表C语言
合并两个有序链表,可以使用递归或迭代的方式实现。下面是使用迭代的方式实现的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 创建链表节点
struct ListNode* createNode(int val) {
struct ListNode *newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 定义头结点和尾节点
struct ListNode *head = createNode(-1);
struct ListNode *tail = head;
// 比较两个链表的节点值,将小的节点加入新链表中
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 将剩余的节点加入新链表中
if (l1) {
tail->next = l1;
} else {
tail->next = l2;
}
// 返回新链表的头结点
return head->next;
}
// 打印链表
void printList(struct ListNode *head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
// 创建两个有序链表
struct ListNode *l1 = createNode(1);
l1->next = createNode(2);
l1->next->next = createNode(4);
printf("l1: ");
printList(l1);
struct ListNode *l2 = createNode(1);
l2->next = createNode(3);
l2->next->next = createNode(4);
printf("l2: ");
printList(l2);
// 合并两个有序链表
struct ListNode *newList = mergeTwoLists(l1, l2);
printf("newList: ");
printList(newList);
return 0;
}
```
在上面的代码中,我们定义了一个`ListNode`结构体表示链表节点,其中包含一个整数值和一个指向下一个节点的指针。`createNode()`函数用于创建一个新的节点,`mergeTwoLists()`函数用于合并两个有序链表,`printList()`函数用于打印链表的值。
在`mergeTwoLists()`函数中,我们首先创建了一个头结点和一个尾节点,将它们都指向头结点。然后我们比较两个链表的节点值,将小的节点加入新链表中,直到其中一个链表为空。最后我们将剩余的节点加入新链表中,最终返回新链表的头结点。
在`main()`函数中,我们创建了两个有序链表,并打印它们的值。然后调用`mergeTwoLists()`函数将它们合并成一个新的有序链表,并打印新链表的值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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_column_c1.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)