中国建设劳动学会是假网站吗,个人网站模板html5,图片分类展示网站源码,南开区网站建设力扣网 21合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 思路分析
最基本的一种思路就是#xff0c;遍历两个链表#xff0c;将对应结点的值进行比较#xff0c;题目要求是要升序排…力扣网 21合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 思路分析
最基本的一种思路就是遍历两个链表将对应结点的值进行比较题目要求是要升序排序即较小的值先排在前面随后所在链表的较小结点先走将后面的值于第二个链表的结点进行比较即谁小谁先排谁小谁先动直到有一个指针遍历为空为止。
需要注意的是
会存在比较存放完后其中一个链表会有剩余此时不需要再进行比较直接进行存放即可。
完整代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* newhead(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位struct ListNode* cur1list1,*cur2list2;//避免头结点丢失使用两个指针代替遍历struct ListNode* tailnewhead;//哨兵位结点同样如此while(cur1cur2)//任意一方为空停止{if(cur1-valcur2-val)//1大于2的情况{tail-nextcur2;//哨兵位不存放有效值从它的下一个结点开始存放。cur2cur2-next;tailtail-next;}else//1小于2的情况{tail-nextcur1;tailtail-next;cur1cur1-next;}}if(cur1NULL)//判断是否存在任一链表有剩余的情况直接存放即可{while(cur2){tail-nextcur2;cur2cur2-next;tailtail-next;}}else{while(cur1){tail-nextcur1;cur1cur1-next;tailtail-next;}}tail-nextNULL;//存放完后tail记得置空否则为野指针struct ListNode* ansnewhead-next;//动态申请的内存空间一定要释放否则会造成内存泄漏free(newhead);return ans;}
实现细节
这里避免使用头结点而采用一个不存放有效值的结点当作哨兵位就不用考虑头结点为空的情况而是直接存放。
动态申请的内存空间不要忘记释放。
