合并两个有序链表

力扣（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<=cur1if(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;
}