上一篇博客我們已經完成了鏈表的所有內容，那么這一篇博客我們來看一下三個特別有意思的鏈表題目。

**第一個題目如下：**

相信不少朋友看到這題目就已經暈了，那就簡單說明下這個題目，題目就是創建一個鏈表，其中每個節點有兩部分–指針域與數值域，指針域里也有兩個指針next（指向下一個節點），random（隨機指向），要求我們拷貝一份這個鏈表，使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態。復制鏈表中的指針都不應指向原鏈表中的節點 。

也就是上圖的形式，這個題目如果單純的只拷貝一份鏈表和每個節點的val，相信大家可以很快的做出，也就是遍歷一下原鏈表，遍歷一個節點創建一個新的節點并拷貝值，最后將節點連接形成鏈表即可。但現在增加了一個random指針，我們該如何解決這個問題呢？

受限于當前的知識，我們可用的方法很少，下面是一個很巧妙的思路：
1、創建新的節點，構造新鏈表

我們可以遍歷一個節點拷貝一個節點，并且將這個新的節點插入至原節點的后面。

2、完成random的指向

當我們把這一步以圖像的形式展現，我們就可以發現新鏈表當前節點的random指針是不是指向原鏈表原節點的random->next指向的節點。

3、取下拷貝的節點，形成題目要求的鏈表

把這個節點連接形成新的鏈表，我們可以使用之前學過的尾插，頭插都是可以的。

最后還有一個小細節，就是如果我們只取下節點，那原鏈表是不是被我們斷開了，我們可以恢復原鏈表的結構也可以不恢復，題目里沒有說明就不用管。

代碼如下：

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
struct Node* copyRandomList(struct Node* head) {struct Node*pcur=head;//創建遍歷原鏈表的指針pcurwhile(pcur){struct Node*newnode=(struct Node*)malloc(sizeof(struct Node));newnode->val=pcur->val;newnode->next=pcur->next;pcur->next=newnode;pcur=newnode->next;}//這一部分就是拷貝節點，并插入原節點后面struct Node*cur=head;//同樣為遍歷鏈表的節點while(cur){struct Node*newnode=cur->next;if(cur->random==NULL){newnode->random=NULL;}else{newnode->random=cur->random->next;}cur=newnode->next;}//這一部分完成的是新節點的random的指向struct Node*phead=NULL;//創建一個新的鏈表phead為頭指針,ptail為尾指針struct Node*ptail=NULL;struct Node*Cur=head;while(Cur){struct Node*node=Cur->next;//node指向的是原鏈表的新節點struct Node*next=node->next;//next指向的是原鏈表的原節點if(ptail==NULL)//如果新鏈表為空{phead=ptail=node;}else//鏈表不為空{ptail->next=node;ptail=ptail->next;}Cur=next;}return phead;//返回新鏈表的頭}

**第二個題目如下：**

這道題目代碼比較簡單，想要理解透徹還是有一定難度的。

思路如下：

就是使用快慢指針，快指針一步走兩個節點，慢指針一步走一個節點，讓慢指針去追這個快指針，當追上的時候也就是fast==slow，那就證明帶環，如果一直追不上那就不帶環。

那一定追的上嗎？有沒有可能出現錯過的情況？快指針可以一步走三個節點嗎？走三個節點會不會錯過呢？這幾個問題就是我們現在需要解決的。

第一個問題：那一定追的上嗎？有沒有可能出現錯過的情況？

從現在開始，fast走兩步，slow走一步，那么兩指針每走一步，它們之間的距離減小1，所以N取任何值slow與fast指針都會相遇，故不存在錯過的情況。

第二個問題：快指針可以一步走三個節點嗎？走三個節點會不會錯過呢？

由上面的圖我們可以推出：

那么我們可以總結一下：
當N為偶數時，無論R為奇數偶數，都能夠追上，也就是不會錯過。
當N為奇數，R為奇數時，能夠追上；
當N為奇數，R為偶數時，永遠追不上。

但是存不存在N為奇數，R為偶數這種情況？

由上面得出的結論就是fast一步走三個節點，一定能追上。

根據上面的推導過程，fast一步走4個節點、5個節點都是可以推出來的。

代碼實現很簡單：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode*fast=head;struct ListNode*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;
}

**第三個題目：**

這個題目就是在上一個題目的基礎上更加深入一點，需要我們返回這個循環的初始節點；

第一步：判斷環的有無
因為這一步與上一個題目基本一樣，所以我這里就不再重復了；

第二步：讓slow走到fast的位置，也就是讓兩個指針相遇定義為meet，返回當前節點，這一步也可以通過前一個題目實現；

第三步：讓pcur從鏈表的頭開始走，同時meet也開始在環內走，當兩者相等時，兩指針指向的節點就是開始循環的節點。

下面我們就來討論為什么：

代碼實現：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode*fastnode(struct ListNode*head)
{struct ListNode*fast=head;struct ListNode*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){return fast;//這里我沒有創建新的meet指針，當兩者相等時，返回其中一個效果相同}}return NULL;//判斷是否有環
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fast=fastnode(head);if(fast==NULL)//如果鏈表沒有環就直接返回NULL{return NULL;}struct ListNode*slow=head;while(slow!=fast)//這一步就是讓兩指針相遇，返回相遇時的節點，也就是環開始的節點{slow=slow->next;fast=fast->next;}return fast;
}

最后一個題還有一種做法，那就是將meet指向的節點斷開，那現在整個題目就變為了相交鏈表求相交節點的問題了，這里只簡單的說明一下思路，有興趣的可以下來實現一下；