给定两个链表,每个链表都已经按升序排列,设计算法实现将两个链表合并到一个升序链表中,返回合并后的链表。
时间: 2023-04-26 16:03:28 浏览: 70
可以使用双指针法,分别指向两个链表的头节点,比较两个节点的值,将较小的节点加入到新的链表中,并将指针向后移动。直到其中一个链表为空,将另一个链表剩余的节点加入到新的链表中即可。最后返回新的链表即为合并后的升序链表。
相关问题
用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;
}
```
将两个升序链表合并为一个新的升序链表并返回
题目描述:
将两个升序链表合并为一个新的升序链表并返回。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
解题思路:
使用双指针法,将两个链表中的节点逐一比较,将较小的节点加入到新的链表中,直到其中一个链表为空,再将另一个链表中剩余的节点加入到新的链表中。
代码实现:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(); // 新链表的虚拟头节点
ListNode* cur = dummy; // 新链表的当前节点
while (l1 && l2) { // 两个链表都不为空时
if (l1->val < l2->val) { // l1的节点值小于l2的节点值
cur->next = l1; // 将l1的节点加入到新链表中
l1 = l1->next; // l1指针后移
} else { // l2的节点值小于等于l1的节点值
cur->next = l2; // 将l2的节点加入到新链表中
l2 = l2->next; // l2指针后移
}
cur = cur->next; // 新链表的当前节点后移
}
cur->next = l1 ? l1 : l2; // 将剩余的节点加入到新链表中
return dummy->next; // 返回新链表的头节点
}
};