一.题目及剖析
https://leetcode.cn/problems/merge-two-sorted-lists/description/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
代码语言：javascript复制输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]示例 2：
代码语言：javascript复制输入：l1 = [], l2 = []
输出：[]示例 3：
代码语言：javascript复制输入：l1 = [], l2 = [0]
输出：[0]提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
二.思路引入
用指针遍历两个链表并实时比较,较小的元素进行尾插,然后较小元素的指针接着向后遍历
三.代码引入
代码语言：javascript复制/**
* 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;
}四.扩展
当然,这道题的思路并不止一种,这种思路是一般方法,我们还可以用递归去写
代码语言：javascript复制/**
* 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;
}
}
