合并两个有序链表
链表 两个 合并 有序
2023-09-14 09:02:34 时间
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
c++代码:
思路1:开辟一个新链表用来存放新的合并后的升序链表,每一次从l1和l2链表分别取出来一个节点,判断两个节点的值哪一个大,大的节点跟在小的节点后面,小的节点尾插到新链表后面,并且还有判断l1和l2哪个链表长度更长,当出现一个链表遍历完后,另一个链表剩余部分就直接尾插到新链表后面
#include<iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
//整合的新链表没有头结点
ListNode* newList = new ListNode();//该链表用来存放整合后的数据
ListNode* end = newList;//指向当前链表尾节点
ListNode* new2 = new ListNode(l1->val > l2->val ? l1->val : l2->val);//取较大的值
ListNode* new1 = new ListNode(l2->val < l1->val ? l2->val : l1->val, new2);//那么取较小的值,并且直接指向较大值的节点
newList->val = new1->val;
end->next = new2;
end = new2;
l1 = l1->next;
l2 = l2->next;
while (l1 != NULL&& l2 != NULL)
{
//这边新链表插入数据使用尾插法
new2 = new ListNode(l1->val>l2->val?l1->val:l2->val);//取较大的值
new1 = new ListNode(l2->val<l1->val?l2->val:l1->val,new2);//那么取较小的值,并且直接指向较大值的节点
end->next = new1;
end = new2;
l1 = l1->next;
l2 = l2->next;
}
//若l1链表比较短,那l2剩余节点直接尾插到新链表尾部,同理l2较短也是如此
if (l1 == NULL)
{
while (l2 != NULL)
{
ListNode* newL2 = new ListNode(l2->val);
end->next = newL2;
end = newL2;
l2 = l2->next;
}
}
if (l2 == NULL)
{
while (l1 != NULL)
{
ListNode* newL1 = new ListNode(l1->val);
end->next = newL1;
end = newL1;
l1 = l1->next;
}
}
return newList;
}
};
//测试-----------------
//为链表赋值---l链表没有头结点
void input(ListNode* l)
{
//输入-1结束赋值
int num = 0;
cin >> num;
if (num == -1)
return;
l->val = num;
//尾插法
ListNode* end = l;
while (1)
{
cin >> num;
if (num == -1)
return;
ListNode* newnode =new ListNode(num);
end->next = newnode;
end = newnode;
}
}
//打印输出链表
void display(ListNode* l)
{
if (l == NULL)
return;
cout << l->val;
display(l->next);
}
void test()
{
ListNode* l1 = new ListNode();
ListNode* l2 = new ListNode();
cout << "请为l1链表赋值:" << endl;
input(l1);
cout << "输出l1链表: " << endl;
display(l1);
cout << endl;
cout << "请为l2链表赋值:" << endl;
input(l2);
cout << "输出l2链表: " << endl;
display(l2);
cout << endl;
cout << "l1和l2链表结合后的结果为:" << endl;
Solution s;
ListNode* l3= s.mergeTwoLists(l1, l2);
display(l3);
cout << endl;
}
int main()
{
test();
system("pause");
return 0;
}
递归写法
class Solution {
public:
//递归写法
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
if (l1 == NULL)//如果l1链表先遍历完,那就返回当前l2链表
return l2;
if (l2 == NULL)
return l1;
if (l1->val <= l2->val)
{
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
};
相关文章
- 两个有序链表的合并
- 浙江大学数据结构习题:02-线性结构1 两个有序链表序列的合并 (15分)
- 找两个链表的公共节点
- 合并两个有序链表
- Java实现 LeetCode 21 合并两个有序链表
- Java实现 LeetCode 21 合并两个有序链表
- (剑指Offer)面试题27:二叉搜索树与双向链表
- 每日一道 LeetCode (7):合并两个有序链表
- (剑指Offer)面试题37:两个链表的第一个公共结点
- 21. 合并两个有序链表
- Leetcode.剑指 Offer II 023. 两个链表的第一个重合节点
- 合并两个排序的链表
- 习题 9.11 有两个链表a和b,设结点中包含学号、姓名。从a链表中删去与b链表中有相同学号的那些结点。
- 将一个链表中的结点依照奇偶分成两个链表
- 【Leetcode刷题Python】21. 合并两个有序链表
- 【LeetCode】21. 合并两个有序链表
- 数据结构与算法之链表