前言：
在前面的练习中，我们简单练习了链表的相关题目，今天我们在来做一些拓展！
例题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; }
总结
链表的相关题目到这里就结束了，当然同学们也可以去oj看看其他题：oj题
