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

创始人

2025-05-30 06:42:20

0次

在这里插入图片描述

🚀write in front🚀
📜所属专栏：初阶数据结构
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

在这里插入图片描述

文章目录

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

前言：

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

例题1：

在这里插入图片描述

方法1：

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

首先，我们假设

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

接下来我们通过快慢指针的两个性质（快指针是慢指针步数的两倍，快慢指针最后相遇）列出一个方程：
在这里插入图片描述
由得出的结论我们可以看出，如果让一个指针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：

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

例题2：

在这里插入图片描述
对于这道题目，大家可能最先会想到计数器的方法，通过记录每个random的位置，在拷贝的链表里面找到对于位置依次连接。但是这样会导致时间复杂度非常的低下：O（N^2）

为了降低复杂度，就不得不使用另外一种方法。要降低时间复杂度，我们就希望能快速的找到原节点的拷贝节点。怎么找呢？

1.拷贝节点链接在原节点后面
在这里插入图片描述

2.此时拷贝节点的random就是原节点random->next
在这里插入图片描述

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

完整代码：

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;
}