牛客网刷题-合并两个排序的链表

系统管理员 2024-04-07 15:20 74阅读 0赞

**前言：  
想要学好嵌入式，C语言与数据结构是必要熟练掌握的，而想熟练掌握一门语言，必须经过大量的练习，刷题，至少需要一两万行的代码量，才能具有一定的编程能力，至少拿到一个功能，怎么去用编程语言去实现它，从现在开始我要开启刷题之路，提高自己的编程水平，还有最重要的面试能力。  
推荐一款刷题神器**

#### 导航 ####

*  一.合并两个排序的链表
 *  二.如何高效刷题

## 一.合并两个排序的链表 ##

**题目原型：**  
![在这里插入图片描述][4edddb24b5224010bd075f2665656f9e.png]  
**输入输出示例：**  
![在这里插入图片描述][1a4e84b4b16846fe9e694d53a0295c19.png]  
**1.题目分析：两个有序链表合并成一个新的有序链表，有几种特殊情况当两个链表为空则新链表为空，其中一个链表为空则新链表为另一个不为空的链表。**

**2.解题思路：**  
**逐一比较两个链表中的结点的结点值，取小的尾插到新链表上。**  
![在这里插入图片描述][9c77079dde254661a5ab267a29dee72d.png]

**代码实现：**

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
        
        // write code here
        struct ListNode* cur1=pHead1;
        struct ListNode* cur2=pHead2;
        struct ListNode* phead=NULL,*Ptail=NULL;
        //cur1为空返回cur2，cur2为空返回cur1，cur1，cur2都为空返回空
        if(cur1 ==NULL )
            return cur2;
        if(cur2 == NULL )
            return cur1;
        
        //找小的尾插到新链表
        while(cur1 !=NULL && cur2 !=NULL)
        {
        
           if(cur1->val < cur2->val )
           {
        
               if(phead == NULL)
               {
        
                 Ptail=phead=cur1;
               } 
               else
               {
        
                 Ptail->next=cur1;
                 Ptail=cur1;  
               }  
               cur1=cur1->next; 
           }
           else
           {
        
              if(phead == NULL)
               {
        
                 Ptail=phead=cur2;
               } 
               else
               {
        
                 Ptail->next=cur2;
                 Ptail=cur2;  
               }  
               cur2=cur2->next;    
           }
        }
        //如果cur1为空将cur2后面的结点全部尾插到新链表
        //如果cur2为空将cur1后面的结点全部尾插到新链表
        if(cur1 == NULL)
            Ptail->next=cur2;
        else
            Ptail->next=cur1;
        
        return phead; 
    }

**上面的代码虽然可以跑过，但是每次进入循环都要判断新链表是否为空(插入第一个结点)有点浪费CPU，其实我们只需要判断一次，让新链表首先插入一个结点，则后面插入结点直接尾插结点就好了。**

*  **优化1:在新链表中先插入一个结点**  
    ![在这里插入图片描述][aa099a0f92c04d70a07ab66f459f821d.png]  
    **优化代码1:**

//优化1:提出循环外
    struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
        
        // write code here
        struct ListNode* cur1=pHead1;
        struct ListNode* cur2=pHead2;
        struct ListNode* phead=NULL;
        struct ListNode* Ptail=NULL;
        if(cur1 ==NULL )
            return cur2;
        if(cur2 == NULL )
            return cur1;
        if( cur1->val < cur2->val )
        {
        
            Ptail=phead=cur1;
            cur1=cur1->next;
        }  
        else
        {
        
            Ptail=phead=cur2;
            cur2=cur2->next;
        }
        while(cur1 !=NULL && cur2 !=NULL)
        {
        
           if(cur1->val < cur2->val )
           {
        
               Ptail->next=cur1;
               cur1=cur1->next; 
           }
           else
           {
        
               Ptail->next=cur2;
               cur2=cur2->next;    
           }
              Ptail=Ptail->next;
        }
        if(cur1 == NULL)
            Ptail->next=cur2;
        else
            Ptail->next=cur1;
        
        return phead; 
    }

*  **优化2:将新链表设计成一个带头结点的链表**  
    ![在这里插入图片描述][9a8e71e5128d4b11a9bbb14cbbd565a4.png]  
    **优化代码2:**

//优化2:添加头结点
    struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
        
        // write code here
        struct ListNode* cur1=pHead1;
        struct ListNode* cur2=pHead2;
        struct ListNode* Ptail=NULL,*phead=NULL;
        phead=Ptail=(struct ListNode*)malloc(sizeof(struct ListNode));
        //cur1为空返回cur2，cur2为空返回cur1，cur1，cur2都为空返回空
        if(cur1 ==NULL )
            return cur2;
        if(cur2 == NULL )
            return cur1;
        //找小的尾插到新结点
        while(cur1 !=NULL && cur2 !=NULL)
        {
        
           if(cur1->val < cur2->val )
           {
        
               Ptail->next=cur1;
               cur1=cur1->next; 
           }
           else
           {
        
               Ptail->next=cur2;
               cur2=cur2->next;    
           }
             Ptail=Ptail->next;;
        }
        //如果cur1为空将cur2后面的结点全部尾插到新链表
        //如果cur2为空将cur1后面的结点全部尾插到新链表
        if(cur1 == NULL)
            Ptail->next=cur2;
        else
            Ptail->next=cur1;
        //记录第一个有效结点，释放头结点
        struct ListNode* first=phead->next;
        free(phead);
        return first; 
    }

## 二.如何高效刷题 ##

如何刷题：  
**1.如果你是基础不太好，可以先按照题解，跟着手打代码，重点理解题目思路，将题目所用到的知识点，解题技巧提炼出来（锻炼代码能力，解题思路）。**![在这里插入图片描述][6680fb10768c48a89fbf9725fd9aa106.png]  
**2.当有一定的代码能力之后，但是看题还是没有思路，可以先看解题思路理解它，然后尝试用代码去实现它。(主要锻炼代码能力，进一步锻炼解题思维)**

**3.拿到一个题目自己先尝试解题，最好是能将解题思路用画图的方式体现出来，这样更能加深印象，然后用代码实现，实现之后再看看题解，或者别人的解题方法，进行对比，找到最优解题思路**  
![在这里插入图片描述][56ec37aa571740aa855ae8794eb3bccf.png]  
**最后：在解题过程中，碰到问题如下图(题目提交后通不过，报错(代码可能有bug)，尽量独立思考，可以先尝试用它的测试用例，一步一步走读代码，看看问题出现在那个地方，如果实在是没有看出来，可以将该函数拷贝到VS中进行调试代码，一定能找出来。（锻炼自己的代码调试能力）**

**总结：  
要想学好嵌入式C语言是根本，但是也离不开数据结构，尤其是链表、队列方面的知识，就接下来我要更新的freerots实时操作系统，就需要用到大量的链表和队列的知识，要想提高自己的编程水平，笔试能力和面试技巧，就得大量刷题手打代码**

[4edddb24b5224010bd075f2665656f9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4a313a06d8a84372baf50eb6f857f643.png
[1a4e84b4b16846fe9e694d53a0295c19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/352dd62f73f24da6bc47351d9b2ff0e8.png
[9c77079dde254661a5ab267a29dee72d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/46980219b29d4a22b8c6617728bb0789.png
[aa099a0f92c04d70a07ab66f459f821d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/ae08a07c4de5453b827ee313317c1f10.png
[9a8e71e5128d4b11a9bbb14cbbd565a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/cc20f7d12eba44eab11de64a809e4ded.png
[6680fb10768c48a89fbf9725fd9aa106.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/bdb378bb166b4d788fb0beaa6d72faaf.png
[56ec37aa571740aa855ae8794eb3bccf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/94067f191ac84253805f5ad623ef37f2.png