连云港百度推广网站建设,公众号推文模板,手机网站管理软件,成都门户网站建设公司题目描述#xff1a;
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1#xff1a;输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]
示例 2#xff1a;输入#xff1a;l1 [], l2 []
输…题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]
示例 2输入l1 [], l2 []
输出[]
示例 3输入l1 [], l2 [0]
输出[0]提示两个链表的节点数目范围是 [0, 50]
-100 Node.val 100
l1 和 l2 均按 非递减顺序 排列
算法一
思路
使用指针法创建新链表逐个存入新链表
代码实现
# includestdlib.hstruct ListNode{int val;struct ListNode *next;
};struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode *newhead(struct ListNode*)malloc(sizeof(struct ListNode));//新链表struct ListNode *prevnewhead;//节点指针while(list1!NULL list2!NULL){//都不为空节点if(list1-val list2-val){//list1小prev-nextlist1;//入新链表list1list1-next;//list1后移}else{//list2prev-nextlist2;list2list2-next;}prevprev-next;//节点指针后移}prev-nextlist1NULL?list2:list1;//取另一个非空的链表节点return newhead-next;//返回头节点指针
}
算法二
思路
使用递归法逐步缩小链表规模
判断链表节点指向值大小小的节点指针后移进行递归最终合并完成
代码实现
# includestdlib.hstruct ListNode{int val;struct ListNode *next;
};struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1NULL){//list1为空节点return list2;//返回list2}else if(list2NULL){//list2为空节点return list1;//返回list1}else if(list1-val list2-val){//list1指向的值更小list1-nextmergeTwoLists(list1-next,list2);//list1-next递归return list1;//返回list1}else{//list2指向的值更小list2-nextmergeTwoLists(list1,list2-next);//list2-next递归return list2;//返回list2}
}
