為了加深對環(huán)形鏈表的理解和掌握，這兩道題是很不錯(cuò)的選擇。
這里所說環(huán)形鏈表不是一個(gè)圈圈的結(jié)構(gòu)，而是帶環(huán)鏈表。

鏈接：環(huán)形鏈表（1）

注意這里鏈表的長度

所以要注意鏈表是否為空
第一種方法，應(yīng)該是比較容易想到的方法（偷雞取腳）
?遍歷鏈表，將每個(gè)節(jié)點(diǎn)的val更改為一個(gè)不容易想到的值，如666666，當(dāng)遇到一個(gè)666666時(shí)就返回true，如果在遍歷過程中一直走到空都再?zèng)]有遇到一個(gè)666666，那就返回false。
代碼如下

bool hasCycle(struct ListNode *head) {struct ListNode*p=head;while(p){if(p->val!=666666){p->val=666666;p=p->next;}else return true;}return false;
}

這種方法明顯是投機(jī)取巧，所以還有可能被抓到。
運(yùn)行后還是也可以通過

雙指針法（正經(jīng)方法）
?就想操場的跑道上，有跑的快的人和跑得慢的人，快的人會(huì)不斷追上慢的人。
?設(shè)置雙指針，從head開始走，快指針一次跑兩步，慢指針一次跑一步，鏈表中是有環(huán)的，快指針一定會(huì)抓到慢指針。
?在慢指針進(jìn)環(huán)時(shí)，快指針已經(jīng)在環(huán)狀里轉(zhuǎn)圈圈了，慢指針一次走一步，快指針一次走兩步，慢指針走半圈，快指針就走一圈。

代碼如下

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

一直找找找，如果有環(huán)一定會(huì)相遇。
思考：

如果快指針一次走3步，還可以保證能抓到慢指針嗎？

?假使慢指針進(jìn)環(huán)時(shí)，快慢指針差距m個(gè)位置，每次快指針與慢指針的距離差距減小為2，有兩種情況。

1. m為偶數(shù)

每次距離都減小2
m-2
m-4
m-6
…
4
2
0
最終快指針會(huì)遇到慢指針。
2. m為奇數(shù)
m-2
m-4
…
3
1
-1
當(dāng)相差為-1時(shí)，快慢指針間的距離變?yōu)榱薽-1。
假設(shè)C是環(huán)的長度，這里的-1即為C-1；如果環(huán)的長度為偶數(shù)，那么快慢指針最近的距離為1，因?yàn)橐淮螠p小的距離為2，所以永遠(yuǎn)也追不上慢指針。

---

環(huán)形鏈表（2）

和第一道題不一樣的是這道題如果有環(huán)，就返回入環(huán)的第一個(gè)節(jié)點(diǎn)，如果鏈表無環(huán)，就返回NULL。
接下來就要進(jìn)行分析
?當(dāng)快指針與慢指針相遇時(shí)，快指針?biāo)叩穆烦淌锹羔樀膬杀丁?br /> ?假設(shè)起點(diǎn)到入環(huán)口的距離是L，圓環(huán)的長度為C，入口點(diǎn)到相遇點(diǎn)的距離為x，這時(shí)通過分析就可以列出一個(gè)等式。

快指針的路程是慢指針的二倍

2(L+X)=L+n( C )+X
可得
L+X=n( C )
L=n( C ）-X;

設(shè)置兩個(gè)指針，第一個(gè)指針從起始位置出發(fā)，另一個(gè)指針從相遇點(diǎn)出發(fā)，他們就會(huì)在環(huán)的入口處相遇。
套用第一道題的思路，快慢指針相遇時(shí)找到相遇點(diǎn)，在設(shè)置兩個(gè)指針分別出發(fā)，直到相遇，如果沒有環(huán)的話就返回NULL;
代碼如下

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

提交后順利通過。

環(huán)形鏈表的約瑟夫問題
鏈接：
環(huán)形鏈表的約瑟夫問題

要使用單向鏈表實(shí)現(xiàn)。
?分析題目，構(gòu)建一個(gè)鏈表，依次儲(chǔ)存節(jié)點(diǎn)的位置，然后找到鏈表的尾，尾的next等于頭節(jié)點(diǎn)，這樣一個(gè)環(huán)形鏈表就構(gòu)建成功了。
?從第一個(gè)節(jié)點(diǎn)開始往后走m-1步（數(shù)數(shù)時(shí)為m，因?yàn)榈谝粋€(gè)節(jié)點(diǎn)數(shù)1，所以往后走m-1到達(dá)目標(biāo)節(jié)點(diǎn)），保存這個(gè)節(jié)點(diǎn)的next，將起始位置更改為該next，然后從新的起始位置繼續(xù)往后邊數(shù)，直到刪除到只剩最后一個(gè)節(jié)點(diǎn)為止，假設(shè)這個(gè)節(jié)點(diǎn)為hei，那么循環(huán)結(jié)束的條件就是hei->next==hei，判斷條件就是hei->next!-hei。

要注意
看代碼，講解很詳細(xì)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef struct ListNode
{int val;struct ListNode* next;
}LN;LN* Initnode()
{LN* head = (LN*)malloc(sizeof(LN));head->next = NULL;head->val = 0;return head;
}LN* GetNewnode(int x)
{LN* newnode = (LN*)malloc(sizeof(LN));newnode->next = NULL;newnode->val = x;return newnode;
}
void Pushnode(LN* head, int x)
{assert(head);LN* pre = head;while (pre->next){pre = pre->next;}pre->next = GetNewnode(x);
}void Popnode(LN*head,LN* node)
{LN* cur = head;while (cur->next != node){cur = cur->next;找到要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)}LN* next = node->next;cur->next = next;free(node);node = NULL;
}int main()
{int m, n;scanf("%d %d", &m, &n);//建立鏈表LN* head = GetNewnode(1);//第一個(gè)編號(hào)為1for (int i = 2; i <= m; i++){Pushnode(head, i);//建立鏈表}//找尾LN* cur = head;while (cur->next != NULL){cur = cur->next;}cur->next = head;//環(huán)形鏈表弄完//數(shù)數(shù)刪位LN* hei = head;while (hei->next != hei){for (int i = 1; i < n; i++)//因?yàn)橐苿?dòng)三步，是移動(dòng)量兩次。{hei = hei->next;}LN* pop = hei;//找到要?jiǎng)h除的節(jié)點(diǎn)pophei = hei->next;//更換hei的位置Popnode(hei,pop);//刪除pop。}printf("%d ", hei->val);//打印留下的節(jié)點(diǎn)的數(shù)值。return 0;
}

本文的講解到這里就結(jié)束啦，鄙人才識(shí)短淺，如有錯(cuò)誤還請多多指教。