21. 合并两个有序链表 - 力扣(LeetCode)
合并两个有序链表我们的思路是创建一个新链表,然后遍历已知的两个有序链表,并比较其节点的val值,将小的尾插到新链表中,然后继续遍历,直到将该两个链表的全部节点全部尾插到新链表中。下面我来画图分析一下如何进行遍历和尾插:
遍历和尾插的过程就如上图一般,接下来我们来实现代码。
我们在写代码的时候还应该注意一些特殊情况:有序链表为空的情况。
我们看,对于这两种情况下:如果两个有序链表都为空,那么就返回NULL;如果只有一个为空,那就返回另外一个。
分析到这里,我们就可以开始写代码了。(注意:该代码只包含解决该问题的函数部分,不包含主函数内容)
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//有空链表if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//无空链表//创建新链表,遍历两链表ListNode* newlist = NULL;ListNode* newtail = NULL;while(list1 && list2)//这两个链表只要有一个走到了NULL,就说明为NULL的链表已经全部尾插完了{if(list1->val <= list2->val){if(newlist == NULL){//新链表为空newlist = list1;newtail = list2;}else{//新链表不为空newtail->next = list1;newtail = newtail->next;}//尾插完后,遍历下一个节点list1 = list1->next;}else{if(newlist == NULL){//新链表为空newlist = list1;newtail = list2;}else{//新链表不为空newtail->next = list1;newtail = newtail->next;}//尾插完后遍历下一个节点list2 = list2->next;}}//跳出循环,说明有一个链表已经遍历完了,只需将另一个链表的剩余元素尾插到新链表if(list1 == NULL){//list1遍历完了,将list2尾插到新链表中newtail->next = list2;}else{//list2遍历完了,将list1尾插到新链表中newtail->next = list1;}return newlist;
}
我们写完之后,代码虽然可以成功解决问题,但是其中出现了很多重复的代码。
哨兵位是一个有空间但是没有值的节点,而且是动态开辟的内存空间,所以我们现在就不能直接返回newist了,而是返回newlist->next,但是动态开辟的内存空间我们使用完之后就应该释放掉,所以我们应该先创建一个临时变量将newist->next存起来,然后将newlist释放掉,后返回临时变量。
所以我们要对该代码进行两部分的调整:
部分一:用来解决重复代码
部分二:用来解决动态内存开辟的释放以及哨兵位的引入对返回值的影响
下面附上完整代码:
typedef struct ListNode ListNode;//避免因为类型名长而对其进行重命名
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//有空链表if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//无空链表//创建新链表,遍历两链表ListNode* newlist = (ListNode*)malloc(sizeof(ListNode));ListNode* newtail = newlist;while(list1 && list2)//这两个链表只要有一个走到了NULL,就说明为NULL的链表已经全部尾插完了{if(list1->val <= list2->val){newtail->next = list1;newtail = newtail->next;//尾插完后,遍历下一个节点list1 = list1->next;}else{newtail ->next = list2;newtail = newtail->next;//尾插完后遍历下一个节点list2 = list2->next;}}//跳出循环,说明有一个链表已经遍历完了,只需将另一个链表的剩余元素尾插到新链表if(list1 == NULL){//list1遍历完了,将list2尾插到新链表中newtail->next = list2;}else{//list2遍历完了,将list1尾插到新链表中newtail->next = list1;}ListNode* ret = newlist->next;free(newlist);newlist = NULL;return ret;
}
完!