【数据结构】链表相关题目（中档题）

亦凉 2024-04-27 15:58 67阅读 0赞

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

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

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

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

*  前言：
 *   *  例题1：
     *   *  方法1：
         *  方法2：
     *  例题2：
     *   *  完整代码：
 *  总结

## 前言： ##

在前面的练习中，我们简单练习了链表的相关题目，今天我们在来做一些拓展！

### [例题1：][1] ###

在这里插入图片描述![在这里插入图片描述][057ad541e5f54ceb998e75eb422c9aef.png]  
![在这里插入图片描述][400e2483f854440da1208efb104fa248.png]

#### 方法1： ####

在上一篇博客里面，我们讲述了快慢指针的概念：通过步长的差异处理环的问题。而这道题我们要寻找入口点，我们该如何处理呢？

首先，我们假设

*  起始点到入口的长度为L，
 *  入口到相遇点的距离为X，
 *  环的长度为C。

接下来我们通过快慢指针的两个性质（快指针是慢指针步数的两倍，快慢指针最后相遇）列出一个方程：  
![在这里插入图片描述][79d4921e95b344968b5cd2d4e419c45c.png]  
  由得出的结论我们可以看出，如果让一个指针a从起点出发，另一个指针b从相遇点出发，如果是闭环，则他们一定会相遇！（这里我们并不需要算出n的值，因为n的值是是让a指针多走n-1个整圈，不影响和b指针相遇）。  
下面我们来看看代码：

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

#### 方法2： ####

如果同学们在做题时无法自己推出这个结论，那么此时我们也可以将相遇点断开，此时就变成了寻找公共节点的题目了。  
![在这里插入图片描述][7f2e8a0fba5f4ed99699c2fe2a40ac64.png]

### [例题2：][2] ###

![在这里插入图片描述][0b5d14f250634f0096a49c2669d0f03a.png]  
对于这道题目，大家可能最先会想到计数器的方法，通过记录每个random的位置，在拷贝的链表里面找到对于位置依次连接。但是这样会导致时间复杂度非常的低下：O（N^2）  
![在这里插入图片描述][f92dbcc62b0540f6bac0b12ca84caf61.png]  
为了降低复杂度，就不得不使用另外一种方法。要降低时间复杂度，我们就希望能快速的找到原节点的拷贝节点。怎么找呢？

1.拷贝节点链接在原节点后面  
![在这里插入图片描述][0e6d5f63cd1a494191700f18c893e24e.png]  
![在这里插入图片描述][78699b74be3c4837b783c699e2912820.png]

2.此时拷贝节点的random就是原节点random->next  
![在这里插入图片描述][bc677c80a62a4a2eb685d4a7c8c258f6.png]  
![在这里插入图片描述][35a8fc1afba743998770432f0e5e4518.png]

3.拷贝节点解下来，链接成新链表，最后将原链表还原。  
![在这里插入图片描述][e33420051c2a4e8b97205e84dcdd6876.png]  
![在这里插入图片描述][b41464ca2b23466f9236a80015b034c7.png]

#### 完整代码： ####

struct Node* copyRandomList(struct Node* head) 
    {
        
    	//第一步
        struct Node*cur=head;
        while(cur)
        {
        
            struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
            struct Node* next=cur->next;
    
            cur->next=newnode;
    
            newnode->next=next;
            newnode->val=cur->val;
    
            cur=next;
        }
        //第二步
        cur=head;
        while(cur)
        {
        
            struct Node*prev=cur->next;
            if(cur->random==NULL)
            {
        
                prev->random=NULL;
            }
            else
            {
        
                prev->random=cur->random->next;
            }
            cur=cur->next->next;
        }
        //第三步
        struct Node* newhead=NULL,*newtail=NULL;
        cur=head;
        while(cur)
        {
        
            struct Node*prev=cur->next;
            struct Node*next=prev->next;
            if(newhead==NULL)
            {
        
                newhead=newtail=prev;
            }
            else
            {
        
                newtail->next=prev;
                newtail=prev;
            }
            cur=next;
        }
        return newhead;
    }

## 总结 ##

链表的相关题目到这里就结束了，当然同学们也可以去oj看看其他题：[oj题][oj]  
  更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][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/e9ad191eedbf48c18a1a74d30d624bc3.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/8c09090806fd4f6c8e9ca9d7f813dfa9.gif
[1]: https://leetcode.cn/problems/linked-list-cycle-ii/description/
[057ad541e5f54ceb998e75eb422c9aef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/d45ad598d9404faaba267c2606a614f9.png
[400e2483f854440da1208efb104fa248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/3fbcf77e6fcb47ab87c86482fdcf93cb.png
[79d4921e95b344968b5cd2d4e419c45c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/17e1e4dcdc1949ee8cfe71f129d1cd2e.png
[7f2e8a0fba5f4ed99699c2fe2a40ac64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/c8a55348b44d4fae95860a3702a90f26.png
[2]: https://leetcode.cn/problems/copy-list-with-random-pointer/description/
[0b5d14f250634f0096a49c2669d0f03a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/9191f321ffaa422099391f79ad99fb26.png
[f92dbcc62b0540f6bac0b12ca84caf61.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/8fddd2200f154d8486337b1523f98917.png
[0e6d5f63cd1a494191700f18c893e24e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/ab22b67abbc34d22ac52f49b8d0a002c.png
[78699b74be3c4837b783c699e2912820.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/8a4d84490ad348f08e153523a41bc2ec.png
[bc677c80a62a4a2eb685d4a7c8c258f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/55fd6e2d540541da95d27dfe270868ac.png
[35a8fc1afba743998770432f0e5e4518.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/b0284ba26a764fffa034e7faa40fda01.png
[e33420051c2a4e8b97205e84dcdd6876.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/f33c028f8c8f493d9cbf207a875480e3.png
[b41464ca2b23466f9236a80015b034c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/55ebdc4f0c374adabe4de2a2a11914a4.png
[oj]: https://leetcode.cn/ag/linked-list/problemset/
[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/85357a8c82ed41ecb21d6b2131c313e8.gif