天津市网站制作建设推广公司,网站建设公司与前端,app开发做网站,凡客诚品服装购物网原题链接#xff1a;https://leetcode.cn/problems/merge-two-sorted-lists/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
可以先创建一个空链表#xff0c;然后依次从两个有序链表中选取最小的进行尾插操作。#xff08;有点类似双…原题链接https://leetcode.cn/problems/merge-two-sorted-lists/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
可以先创建一个空链表然后依次从两个有序链表中选取最小的进行尾插操作。有点类似双指针的操作~
我们可以用不带哨兵位和带哨兵位两种方法实现
不带哨兵位
如果两个链表有一个为空直接返回另一个链表即可。
如果两个链表都是非空的我们就创建一个结构体指针head和一个结构体指针tail都初始化为空指针NULL之后分别用来指向新链表的头和尾。
同时遍历两个链表当有一个链表遍历完时停止。这里使用while(list1list2)进行循环。
当空链表插入第一个结点也就是tailNULL时需要单独考虑让头指针head和尾指针next都指向此时值较小的那个结点即可。
其他情况正常尾插即可就是让tail-next指向值较小的结点。之后让tail指向当前插入的结点也就是让tail往后走一步然后让相对应的list1或者list2往后走一步即可。
因为有可能while循环结束时还有链表的结点没有被插入到新链表。所以我们要用if语句判断将剩余的结点直接插入到新链表。
最后我们返回头指针head即可。 带哨兵位
带哨兵位最大的好处是方便尾插不用单独考虑在新链表插入第一个结点时的情况了因为带哨兵位让每一个结点地位都一样了。
这里相比不带哨兵位多的一些操作就是要先用malloc()函数申请一个结点作为哨兵位让head和tail一开始都直接指向这个结点。
当完成合并操作后让头指针head往后走一步指向哨兵位后面一个结点。
然后使用free()释放掉哨兵位。
最后返回head即可。 3. 代码实现
不带哨兵位
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1NULL)return list2;if(list2NULL)return list1;struct ListNode *headNULL,*tailNULL;while(list1list2){if(list1-vallist2-val){if(tailNULL){headtaillist1;}else{tail-nextlist1;tailtail-next;}list1list1-next;}else{if(tailNULL){headtaillist2;}else{tail-nextlist2;tailtail-next;}list2list2-next;}}if(list1)tail-nextlist1;if(list2)tail-nextlist2;return head;
} 带哨兵位
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1NULL)return list2;if(list2NULL)return list1;struct ListNode *headNULL,*tailNULL;//带一个哨兵位方便尾插headtail(struct ListNode*)malloc(sizeof(struct ListNode));while(list1list2){if(list1-vallist2-val){tail-nextlist1;tailtail-next;list1list1-next;}else{tail-nextlist2;tailtail-next;list2list2-next;}}if(list1)tail-nextlist1;if(list2)tail-nextlist2;struct ListNode *delhead;headhead-next;free(del);return head;
}
