目录
一.题目及剖析
二.思路引入
三.代码引入
四.扩展
一.题目及剖析
https://leetcode.cn/problems/merge-two-sorted-lists/description/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = [] 输出:[]
示例 3:
输入:l1 = [], l2 = [0] 输出:[0]
提示:
- 两个链表的节点数目范围是
[0, 50]
-100 <= Node.val <= 100
-
l1
和l2
均按 非递减顺序 排列
二.思路引入
用指针遍历两个链表并实时比较,较小的元素进行尾插,然后较小元素的指针接着向后遍历文章来源:https://www.toymoban.com/news/detail-830045.html
三.代码引入
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode *newHead, *newTail, *l1, *l2;
newHead = newTail = (struct ListNode*)malloc(sizeof(struct ListNode));
l1 = list1;
l2 = list2;
if(list1 == NULL)
return list2;
if(list2 == NULL)
return list1;
while(l1 && l2)
{
if(l1->val > l2->val)
{
newTail->next = l2;
newTail = newTail->next;
l2 = l2->next;
}
else
{
newTail->next = l1;
newTail = newTail->next;
l1 = l1->next;
}
}
if(l1)
newTail->next = l1;
if(l2)
newTail->next = l2;
return newHead->next;
}
四.扩展
当然,这道题的思路并不止一种,这种思路是一般方法,我们还可以用递归去写文章来源地址https://www.toymoban.com/news/detail-830045.html
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
//递归条件
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}
else{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
到了这里,关于Leecode之合并两个有序链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!