c语言练习91：合并两个有序链表

合并两个有序链表

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码1：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //判断链表是否为空 if(list1==NULL){ return list2; } if(list2==NULL){ return list1; } //走到这里说明链表不为空，遍历链表 ListNode*cur1=list1; ListNode*cur2=list2; ListNode*newhead,*newtail; newhead=newtail=NULL; while(cur1&&cur2){ //1.空链表的情况下：插入的结点就是链表的头结点和尾结点 //2.非空链表：插入的结点是链表的新的尾结点，头结点不变 if(cur1->val<cur2->val){ if(newhead==NULL){ newhead=newtail=cur1; } else{ newtail->next=cur1; newtail=newtail->next; } cur1=cur1->next; } else{//cur2<=cur1 if(newhead==NULL){ newhead=newtail=cur2; } else{ newtail->next=cur2; newtail=newtail->next; } cur2=cur2->next; } } if(cur1){ newtail->next=cur1; } if(cur2){ newtail->next=cur2; } return newhead; }

优化：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //判断链表是否为空 if(list1==NULL){ return list2; } if(list2==NULL){ return list1; } //走到这里说明链表不为空，遍历链表 ListNode*cur1=list1; ListNode*cur2=list2; ListNode*newhead,*newtail;//newhead为哨兵卫 newhead=newtail=(ListNode*)malloc(sizeof(ListNode)); // ListNode*newhead,*newtail; // newhead=newtail=NULL; while(cur1&&cur2){ //1.空链表的情况下：插入的结点就是链表的头结点和尾结点 //2.非空链表：插入的结点是链表的新的尾结点，头结点不变 if(cur1->val<cur2->val){ // if(newhead==NULL){ // newhead=newtail=cur1; // } // else{ // newtail->next=cur1; // newtail=newtail->next; // } newtail->next=cur1; newtail=newtail->next; cur1=cur1->next; } else{ //cur2<=cur1 // if(newhead==NULL){ // newhead=newtail=cur2; // } // else{ // newtail->next=cur2; // newtail=newtail->next; // } newtail->next=cur2; newtail=newtail->next; cur2=cur2->next; } } if(cur1){ newtail->next=cur1; } if(cur2){ newtail->next=cur2; } ListNode*returnhead=newhead->next; free(newhead); return returnhead; }