两个有序线性链表合并
时间: 2023-12-12 12:03:57 浏览: 29
将两个有序线性链表合并的算法可以采用递归或迭代的方式实现。以下是迭代的实现方式:
```python
def merge_sorted_lists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return dummy.next
```
其中,ListNode 是链表节点的定义,val 表示节点的值,next 表示指向下一个节点的指针。
相关问题
两个有序链表的合并操作
两个有序链表的合并操作可以通过迭代或递归的方式完成。
1. 迭代法:
- 创建一个新的链表作为结果链表。
- 比较两个链表的当前节点,将较小的节点加入结果链表,并将当前链表指针后移一位。
- 重复上一步,直到其中一个链表为空。
- 将另一个非空链表的剩余部分直接加入结果链表。
- 返回结果链表。
2. 递归法:
- 判断两个链表是否为空,如果有一个为空,则返回另一个链表。
- 比较两个链表的当前节点,将较小的节点作为合并后的链表的当前节点。
- 递归调用合并函数,将较小节点的下一个节点与另一个链表的当前节点进行比较,并将较小的节点作为下一个节点。
- 返回合并后的链表。
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* dummy = createNode(0);
// 用于遍历新链表和两个原始链表
struct ListNode* cur = dummy;
while (l1 != NULL && l2 != NULL) {
// 比较两个节点的值
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
// 将剩余链表的节点直接添加到新链表的末尾
if (l1 != NULL) {
cur->next = l1;
}
if (l2 != NULL) {
cur->next = l2;
}
return dummy->next;
}
// 打印链表
void printList(struct ListNode* head) {
struct ListNode* cur = head;
while (cur != NULL) {
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
int main() {
// 创建两个有序链表
struct ListNode* l1 = createNode(1);
l1->next = createNode(3);
l1->next->next = createNode(5);
struct ListNode* l2 = createNode(2);
l2->next = createNode(4);
l2->next->next = createNode(6);
// 合并两个有序链表
struct ListNode* mergedList = mergeTwoLists(l1, l2);
// 打印合并后的链表
printf("Merged List: ");
printList(mergedList);
return 0;
}
```
运行上述代码,输出结果为:
```
Merged List: 1 2 3 4 5 6
```
这是将两个有序链表合并成一个有序链表的基本思路和实现方法。希望对你有帮助!