力扣网 21合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
思路分析
最基本的一种思路就是，遍历两个链表，将对应结点的值进行比较，题目要求是要升序排序，即较小的值先排在前面，随后所在链表的较小结点先走，将后面的值于第二个链表的结点进行比较，即谁小谁先排，谁小谁先动，直到有一个指针遍历为空为止。
需要注意的是：
会存在比较存放完后，其中一个链表会有剩余，此时不需要再进行比较，直接进行存放即可。
完整代码
代码语言：javascript复制struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位
struct ListNode* cur1=list1,*cur2=list2;//避免头结点丢失，使用两个指针代替遍历
struct ListNode* tail=newhead;//哨兵位结点同样如此
while(cur1&&cur2)//任意一方为空停止
{
if(cur1->val>cur2->val)//1大于2的情况
{
tail->next=cur2;//哨兵位不存放有效值，从它的下一个结点开始存放。
cur2=cur2->next;
tail=tail->next;
}
else//1小于2的情况
{
tail->next=cur1;
tail=tail->next;
cur1=cur1->next;
}
}
if(cur1==NULL)//判断是否存在任一链表有剩余的情况，直接存放即可
{
while(cur2)
{
tail->next=cur2;
cur2=cur2->next;
tail=tail->next;
}
}
else
{
while(cur1)
{
tail->next=cur1;
cur1=cur1->next;
tail=tail->next;
}
}
tail->next=NULL;//存放完后tail记得置空（否则为野指针）
struct ListNode* ans=newhead->next;//动态申请的内存空间一定要释放，否则会造成内存泄漏
free(newhead);
return ans;
}实现细节
这里避免使用头结点而采用一个不存放有效值的结点当作哨兵位，就不用考虑头结点为空的情况而是直接存放。
动态申请的内存空间不要忘记释放。
