每日一题---OJ题: 合并两个有序链表

嗨!小伙伴们,好久不见啦! 今天我们来看看一道很有意思的一道题---合并两个有序链表

嗯,题目看上去好像不难,我们一起画图分析分析吧!

上图中,list1有3个结点,分别为1,2,3 ; list2中有3个结点,分别为1,3,4, 题目要求我们要将这两个链表合并到一起,并且是升序,最后将链表返回。

思路1：定义2个变量，l1和l2,分别指向list1和list2,它们从头遍历链表,依次比较每个结点的数据域,如果l1指向的结点的数据域小于l2指向的结点的数据域,那么就将l1尾插到新链表中; 反之亦然。

当 l1 && l2 不为空的时候,进入while循环(注意是 &&，因为只要有一个不满足条件，就可以跳出while循环),判断第一个结点,判断完毕后,尾插到新链表中(如果新链表为空,那么这个结点就是链表的头结点和尾结点 ; 如果链表不为空,这个结点就是链表的新的尾结点)。

第一次: 将list2中第一个结点尾插到新链表中,该结点就是链表的头结点和尾结点。l2继续往后遍历链表。

第二次：l1指向的结点的数据域小于l2,因此将该结点尾插到新链表中,这个结点就是链表的新的尾结点，l1指向下一个结点。

第三次：l1指向的结点的数据域小于l2,因此将该结点尾插到新链表中,这个结点就是链表的新的尾结点，l1指向下一个结点。

第四次： l2指向的结点的数据域小于l1,因此将该结点尾插到新链表中,这个结点就是链表的新的尾结点，l2指向下一个结点。

第五次：

第六次:

好啦,大致思路就是这样,接下来我们开始实现吧!

首先,定义2个变量l1和l2,分别指向list1和list2; 其次,我们定义新链表的表头newHead和表尾newTail。

struct ListNode* l1 = list1;                    //定义l1变量,指向list1
struct ListNode* l2 = list2;                    //定义l2变量,指向list2struct ListNode* newHead = NULL;                //定义新链表的头结点
struct ListNode* newTail = NULL;                //定义新链表的尾结点

当 l1 && l2不为空,进入循环,依次比较每一个结点。

 while( l1 && l2){if(l1->val < l2->val){//l1比l2小if(newTail == NULL){//如果链表为空newHead = newTail = l1;}else{//链表不为空newTail->next = l1;newTail = l1;}l1 = l1->next;        //l1指向下一个结点}else{//l2比l1小if(newTail == NULL){//如果链表为空newHead = newTail = l2;}else{//链表不为空newTail->next = l2;newTail = l2;}l2 = l2->next;        //l2指向下一个结点}
}

是不是这里就结束了呢? 当然不是! 当 l1 走到NULL的位置或者 l2 走到空的位置, 会跳出循环,来到后面的代码。

当 l1还未遍历完链表时,我们只需要将 newTail的next指针指向 l1 就可以啦! 用 if条件来做判断,本身就只让它执行一次,因为链表最后剩下的,就直接往后挂了,链表的每一个结点是通过next指针链接的,找到一个结点,就可以找到后续的所有结点。

(就像老鹰捉小鸡一样,是不是从中间折断的话,那后面的那些人还是连在一起的,重新连接的话,那只用把后半段的第一个人找到,挂回去,那后面的人也就一并连接回去了。)

if(l1){//l1没有遍历完链表newTail->next = l1;}if(l2){//l2没有遍历完链表newTail->next = l2;}

好啦,最后我们返回newHead就可以啦! 但是还有一个小小的问题需要注意: 传过来的参数 list1 或者 list2 有可能为空, 因此我们需要在开始就判断一下它们是否为空。

 if(list1 == NULL){//如果list1为空,则返回list2return list2;}if(list2 == NULL){//如果list2为空,则返回list1return list1;}

OK,整体代码如下:

 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 == NULL){//如果list1为空,则返回list2return list2;}if(list2 == NULL){//如果list2为空,则返回list1return list1;}ListNode* l1 = list1;//定义l1变量,指向list1ListNode* l2 = list2; //定义l2变量,指向list2ListNode* newHead = NULL; //定义新链表的头结点ListNode* newTail = NULL; //定义新链表的尾结点while( l1 && l2){if(l1->val < l2->val){//l1比l2小if(newTail == NULL){//如果链表为空newHead = newTail = l1;}else{//链表不为空newTail->next = l1;newTail = l1;}l1 = l1->next;        //l1指向下一个结点}else{//l2比l1小if(newTail == NULL){//如果链表为空newHead = newTail = l2;}else{//链表不为空newTail->next = l2;newTail = l2;}l2 = l2->next;      //l2指向下一个结点}
}if(l1){//l1没有遍历完链表newTail->next = l1;}if(l2){//l2没有遍历完链表newTail->next = l2;}return newHead; //返回头结点
}

好的,这道题我们基本上做完了,可是,看看这代码,好像有重复冗余的部分,我们如何优化代码呢?

答案是: 我们可以定义一个哨兵结点,这个结点可以不存放数据,让它指向新链表的头结点。

    ListNode* node =(ListNode*) malloc(sizeof(ListNode));   //创建一个哨兵结点ListNode* newHead = node;                               //头结点指向哨兵结点ListNode* newTail = node;                               //尾结点指向哨兵结点

中间的循环也需要更改，不用判断链表是否为空了。

 while( l1 && l2){if(l1->val < l2->val){//       //l1比l2小// if(newTail == NULL){//      //如果链表为空//     newHead = newTail = l1;//  }else{//     //链表不为空//     newTail->next = l1;//     newTail = l1;//  }newTail->next = l1;newTail = l1;l1 = l1->next;        //l1指向下一个结点}else{//l2比l1小// if(newTail == NULL){//     //如果链表为空//     newHead = newTail = l2;//    }else{//     //链表不为空//      newTail->next = l2;//      newTail = l2;newTail->next = l2;newTail = l2;l2 = l2->next;      //l2指向下一个结点}
}

malloc了空间,但这块空间实际上用不了,最后我们需要将哨兵结点释放

    //malloc了空间,但这块空间实际上用不了,应该将其释放掉ListNode* ret = newHead->next;free(newHead);return ret; //返回头结点的下一个结点

好啦，优化过的代码如下：

 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 == NULL){//如果list1为空,则返回list2return list2;}if(list2 == NULL){//如果list2为空,则返回list1return list1;}ListNode* l1 = list1;//定义l1变量,指向list1ListNode* l2 = list2; //定义l2变量,指向list2ListNode* node =(ListNode*) malloc(sizeof(ListNode));   //创建一个哨兵结点ListNode* newHead = node;                               //头结点指向哨兵结点ListNode* newTail = node;                               //尾结点指向哨兵结点while( l1 && l2){if(l1->val < l2->val){//       //l1比l2小// if(newTail == NULL){//      //如果链表为空//     newHead = newTail = l1;//  }else{//     //链表不为空//     newTail->next = l1;//     newTail = l1;//  }newTail->next = l1;newTail = l1;l1 = l1->next;        //l1指向下一个结点}else{//l2比l1小// if(newTail == NULL){//     //如果链表为空//     newHead = newTail = l2;//    }else{//     //链表不为空//      newTail->next = l2;//      newTail = l2;newTail->next = l2;newTail = l2;l2 = l2->next;      //l2指向下一个结点}
}//跳出循环存在两种情况,要么l1走到空l2不为空,要么l2走到空,l1不为空
//不可能存在都为空的情况if(l1){//l1没有遍历完链表newTail->next = l1;}if(l2){//l2没有遍历完链表newTail->next = l2;}//malloc了空间,但这块空间实际上用不了,应该将其释放掉ListNode* ret = newHead->next;free(newHead);return ret; //返回头结点的下一个结点
}