【数据结构】链表相关题目（简单版）

小咪咪 2024-04-27 15:58 104阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏： [初阶数据结构][Link 1]  
> ?️博客主页：[睿睿的博客主页][Link 2]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *   *  习题1：
     *  习题2
     *  习题3
     *   *  衍生题1：
         *  衍生题2：
     *  习题4：
     *  习题5：
 *  总结

## 前言 ##

在学完了顺序表的基本知识后，我们可以通过一些习题来巩固所学知识！

### 习题1： ###

删除链表中等于给定值 val 的所有结点。[oj链接][oj]  
![在这里插入图片描述][37238ee94e2b4209a60265a7a8bf2a2d.png]  
这道题目有两种做法：

*  **方法一**：双指针的遍历，通过双指针来查找删除节点并连接后面的节点，但是缺点就是会有特殊情况需要考虑（**头删的情况**），代码如下：  
    ![在这里插入图片描述][21d7f2259fda4fdd9750ce9916689b6b.png]
 *  **方法2**：通过遍历，将节点尾插到新链表，最后返回新链表，代码如下：

struct ListNode* removeElements(struct ListNode* head, int val)
    {
        
        struct ListNode*cur=head,*newnode=NULL,*tail=NULL;
        while(cur)
        {
        
            if(cur->val!=val)
            {
        
                if(newnode==NULL)
                {
        
                    newnode=cur;
                    tail=cur;
                }
                else
                {
        
                    tail->next=cur;
                    tail=tail->next;
                }
              cur=cur->next;
            }
            else
            {
        
                struct ListNode*next=cur;
                cur=next->next;
                free(next);
            }
        }
    if(tail)
    {
        
        tail->next=NULL;
    }
      return newnode;
    }

### 习题2 ###

反转一个单链表。[oj链接][oj 1]  
![在这里插入图片描述][73e6a031c8754f3f96caa48316193590.png]  
这道题也有两种方法，

*  **方法1**：用三指针的方法，前两个来改变每个节点的链接关系，最后一个节点用来标记位置方便遍历链表  
    ![在这里插入图片描述][5532980fc1d34b2cb121ec9a81858d7f.png]  
    代码如下：  
    ![在这里插入图片描述][a19cd8e8352a47ddaaba47163c95066c.png]
 *  **方法2**：取每个节点头插到新链表：

![在这里插入图片描述][3fafbb1c7ae046fc95650eff20f57151.png]

### 习题3 ###

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。[oj链接][oj 2]  
![在这里插入图片描述][9be018be71934794b979ca35cafe881d.png]  
  这里我们就要介绍一下快慢指针了。通过快慢指针我们可以解决很多问题，以后都会用到。  
  那么什么是快慢指针呢？  
  顾名思义，快慢指针就是通过两个不同指针步长的不同来遍历链表。  
![在这里插入图片描述][7c2f94a9ccb54374ba6cef506d691fc4.png]  
  这道题我们让一个指针走两步，一个指针走一步，当快指针指向空或快指针的next指向空的时候，慢指针指向位置就是中间节点位置。

struct ListNode* middleNode(struct ListNode* head)
    {
        
        struct ListNode*slow=head,*fast=head;
    
        while(fast!=NULL&&fast->next!=NULL)
        {
        
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }

#### 衍生题1： ####

输入一个链表，输出该链表中倒数第k个结点。[oj链接][oj 3]  
![在这里插入图片描述][654ceee9441a462f89e0a560c242ea75.png]  
  其实也是快慢指针的思想，只是这里不是步长的不同，而是起点不同：  
  要寻找倒数第k个节点，就让快指针的起点在慢指针的后k步。当快指针指向空的时候，慢指针就指向倒数第k个节点。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
        
        // write code here
        struct ListNode* slow=pListHead;
        struct ListNode* fast=pListHead;
       
        while(k--)
        {
        
           
             if(fast==NULL)
        {
        
            return NULL;
        }
         fast=fast->next;
        }
        while(fast)
        {
        
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }

#### 衍生题2： ####

给定一个链表，判断链表中是否有环。[oj链接][oj 4]  
![在这里插入图片描述][80a44dd6956b4fc485bcb294f0ac3b87.png]  
  这道题也是用快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

那么，为什么快指针每次走两步，慢指针走一步可以？  
  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。  
  此时，**两个指针每移动一次，之间的距离就缩小一步**，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，**快指针肯定是可以追上慢指针的**，即相遇。  
代码如下：

bool hasCycle(struct ListNode *head) 
    {
        
        struct ListNode*fast=head,*slow=head;
        if(head==NULL||head->next==NULL)
        {
        
            return false;
        }
        fast=fast->next;
        while(fast!=slow)
        {
        
            if(fast==NULL||fast->next==NULL)
                break;
            fast=fast->next->next;
            slow=slow->next;
        }
        if(fast==slow)
        return true;
        return false;
    }

### 习题4： ###

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的[oj链表][oj 5]

这道题引入了哨兵位，也就是空的头节点。其实，对于链表尾插的时候，需要判断是否为空，比较麻烦，只要我们创建一个空的头节点就可以避免很多情况。

链表在**头插**的时候我们不需要头节点；  
  链表在**尾插**的有空的头节点会更方便。  
![在这里插入图片描述][98a2550829764ec6a1dee9562410adf9.png]

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
    {
        
        struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode*tail=newnode;
        tail->next=NULL;
        while(list1&&list2)
        {
        
            if(list1->val<list2->val)
            {
        
                tail->next=list1;
                tail=list1;
                list1=list1->next;
            }
            else
            {
        
                tail->next=list2;
                tail=list2;
                list2=list2->next;
            }
        }
    
    if(list1)
        tail->next=list1;
    if(list2)
        tail->next=list2;
    
        return newnode->next;
    }

### 习题5： ###

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。[oj链接][oj 6]

![在这里插入图片描述][c11a8039e7314b57a07577ed47e6bb13.png]  
  这道题我们创建两个新链表（带有哨兵位的空头节点），小于的尾插到一个链表，大于的尾插到另外一个链表，最后将他们连起来即可。

class Partition {
        
    public:
        ListNode* partition(ListNode* pHead, int x) 
        {
        
            // write code here
            struct ListNode*greaternode=NULL;
            struct ListNode*lessnode=NULL,*cur=pHead;
           
            struct ListNode* gtail=greaternode,*ltail=lessnode;
            while(cur!=NULL)
            {
        
                if(cur->val>=x)
                {
        
                    gtail->next=cur;
                    gtail=cur;
                    cur=cur->next;
                    gtail->next=NULL;
                }
                else
                {
        
                    ltail->next=cur;
                    ltail=cur;
                    cur=cur->next;
                    ltail->next=NULL;
                }
            }
            ltail->next=greaternode->next;
            return lessnode->next;
        }
    };

## 总结 ##

还是那句话，数据结构需要多画图，并且对各种情况要有十足的把握才能做对题目。  
  更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 3]  
> [c语言学习][c]  
> [算法][Link 4]  
> [智力题][Link 5]  
> [初阶数据结构][Link 1]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/c5fcc3fc01de4a149de9cb4cec9cf179.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/6503995505fd4da09f2dbb89bff0ad7e.gif
[oj]: https://leetcode.cn/problems/remove-linked-list-elements/description/
[37238ee94e2b4209a60265a7a8bf2a2d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/9e1324b9920944c088a5387dcf759470.png
[21d7f2259fda4fdd9750ce9916689b6b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/4164382b6ad84dd384f10b2f002f97f5.png
[oj 1]: https://leetcode.cn/problems/reverse-linked-list/description/
[73e6a031c8754f3f96caa48316193590.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/19b102de4270400b925e91b541d5c2c2.png
[5532980fc1d34b2cb121ec9a81858d7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/c712f69388c640a9bf5aeddbc402aa4d.png
[a19cd8e8352a47ddaaba47163c95066c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/b7f904e960c84657896e92949d2cc4a5.png
[3fafbb1c7ae046fc95650eff20f57151.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/66ab66d805bf43dd8bfa7ce39c76b1f8.png
[oj 2]: https://leetcode.cn/problems/middle-of-the-linked-list/description/
[9be018be71934794b979ca35cafe881d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/b2560a51a3074f1599fb220d9e572bd5.png
[7c2f94a9ccb54374ba6cef506d691fc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/c8b59820bce94928ae367bc34dc61a5e.png
[oj 3]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[654ceee9441a462f89e0a560c242ea75.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/6ee20c135b1347e4a15385d555c9209d.png
[oj 4]: https://leetcode.cn/problems/linked-list-cycle/description/
[80a44dd6956b4fc485bcb294f0ac3b87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/6f7ce62d01b340d6981caa7a116abf84.png
[oj 5]: https://leetcode.cn/problems/merge-two-sorted-lists/description/
[98a2550829764ec6a1dee9562410adf9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/4081c30ceb9e496f8f1619a83ec3b3b0.png
[oj 6]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[c11a8039e7314b57a07577ed47e6bb13.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/9c6eb40ea38a4b1b89295d492bf3af83.png
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12166402.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/0c5ca6b9d4d64774883b05459f5270fa.gif