赞
踩
题目:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
思路1:带哨兵卫的头节点
定义两个指针 head 和 tail ,比较两个链表中的较小值,放到 tail ->next 中,如果有任意一个链表走到空了,则结束,然后判断找到不为空的链表,把不为空的链表中的数据一次放到新链表中。
画图分析:
代码的实现:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //考虑list1和list2其中一个为空的情况 if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* head=NULL,*tail=NULL; //带哨兵卫的头节点,这个头节点不存储有效数据 head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); //当list1和list2任意一个为空循环就结束 while(list1 && list2) { //head为空的情况上面已经处理了,这里是head不为空的情况的插入数据 if(list1->val < list2->val) { tail->next=list1; tail=list1; list1=list1->next; } else { tail->next=list2; tail=list2; list2=list2->next; } } //如果list1不为空则把list1后面的数据链接到tail->next的后面 if(list1) tail->next=list1; //如果list2不为空则把list2后面的数据链接到tail->next的后面 if(list2) tail->next=list2; //在前面malloc的空间需要释放,释放前先保存head->next的地址 struct ListNode* list=head->next; free(head); return list; }
思路2:不使用带哨兵卫的头节点
画图分析:
代码的实现:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //考虑list1和list2其中一个为空的情况 if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* head=NULL,*tail=NULL; //考虑head为空时插入数据 if(list1->val < list2->val) { head=tail=list1; list1=list1->next; } else { head=tail=list2; list2=list2->next; } //当list1和list2任意一个为空循环就结束 while(list1 && list2) { //head和tail是指向同一块地址的,带哨兵卫的头节点不存储有效数据,所以数据从tail->next开始存 if(list1->val < list2->val) { tail->next=list1; tail=list1; list1=list1->next; } else { tail->next=list2; tail=list2; list2=list2->next; } } //如果list1不为空则把list1后面的数据链接到tail->next的后面 if(list1) { tail->next=list1; } //如果list2不为空则把list2后面的数据链接到tail->next的后面 if(list2) { tail->next=list2; } //返回头节点 return head; }
文章到这就结束啦,有问题的小伙伴可以留言噢,谢谢你的赞!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。