给定两个链表,每个链表都已经按升序排列,设计算法实现将两个链表合并到一个升序链表中,返回合并后的链表。 输入样例: 1 4 5 1 3 6 输出样例: 1 1 3 4 5 6
时间: 2023-05-21 09:02:48 浏览: 37
以下是C知道的回答:
可以使用双指针的方法,分别指向两个链表的头节点,比较两个节点的值,将较小的节点加入到新的链表中,并将指针向后移动。直到其中一个链表为空,将另一个链表剩余的节点加入到新的链表中即可。以下是代码实现:
```
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = NULL;
struct ListNode* cur = dummy;
while(l1 && 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 ? l1 : l2;
return dummy->next;
}
```
其中,dummy节点是为了方便处理头节点而创建的一个虚拟节点。
相关问题
给定两个链表,每个链表都已经按升序排列,设计算法实现将两个链表合并到一个升序链表中,返回合并后的链表。
可以使用双指针法,分别指向两个链表的头节点,比较两个节点的值,将较小的节点加入到新的链表中,并将指针向后移动。直到其中一个链表为空,将另一个链表剩余的节点加入到新的链表中即可。最后返回新的链表即为合并后的升序链表。
用c语言实现给定两个链表,每个链表都已经按升序排列,设计算法实现将两个链表合并到一个升序链表中,返回合并后的链表。
```
#include <stdio.h>
#include <stdlib.h>
/* 链表结构体 */
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
/* 创建链表 */
ListNode* createList(int* nums, int numsSize) {
ListNode* head = NULL;
ListNode* tail = NULL;
for (int i = 0; i < numsSize; i++) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = nums[i];
node->next = NULL;
if (head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = tail->next;
}
}
return head;
}
/* 合并两个链表 */
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = NULL;
ListNode* tail = NULL;
while (l1 != NULL && l2 != NULL) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (l1->val < l2->val) {
node->val = l1->val;
l1 = l1->next;
} else {
node->val = l2->val;
l2 = l2->next;
}
node->next = NULL;
if (head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = tail->next;
}
}
if (l1 != NULL) {
if (head == NULL) {
head = l1;
} else {
tail->next = l1;
}
}
if (l2 != NULL) {
if (head == NULL) {
head = l2;
} else {
tail->next = l2;
}
}
return head;
}
/* 输出链表 */
void printList(ListNode* head) {
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
int nums1[] = {1, 2, 4};
int nums2[] = {1, 3, 4};
ListNode* l1 = createList(nums1, 3);
ListNode* l2 = createList(nums2, 3);
ListNode* merged = mergeTwoLists(l1, l2);
printList(merged);
return 0;
}
```
相关推荐
![](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)
![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)