前言
本系列主要讲解链表的经典题
注：划重点！！必考~
合并两个有序链表
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
示例：
提示：
- 两个链表的节点数目范围是
[0, 50]-100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
解题思路:
如果是到原链表本身上进行合并，则需要考虑的地方会比较多（实现起来很难）
这里我们选择使用尾插法
两个链表进行结点比较，较小的则将该结点进行尾插到另一个新链表上，再比较下一个
比较完一个链表后，另一个链表存在元素未比较，将该链表整体尾插
注：这里我们可以选择双指针尾插，也可以选择带哨兵卫头结点尾插
参考代码：
/** * 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; //创建哨兵卫头结点 struct ListNode*newhead=malloc(sizeof(struct ListNode)); newhead->next=NULL; //遍历指针 struct ListNode*cur1=l1,*cur2=l2,*cur3=newhead; while(cur1&&cur2) { if(cur1->val>cur2->val) { cur3->next=cur2; cur3=cur3->next; cur2=cur2->next; } else { cur3->next=cur1; cur3=cur3->next; cur1=cur1->next; } } //存留节点尾插 if(cur1) { cur3->next=cur1; } if(cur2) { cur3->next=cur2; } //记录哨兵后一个空间，并释放哨兵 struct ListNode*next=newhead->next; free(newhead); return next; }
结果：
