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

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

注意這里鏈表的長度

所以要注意鏈表是否為空
第一種方法，應(yīng)該是比較容易想到的方法（偷雞取腳）
?遍歷鏈表，將每個節(jié)點的val更改為一個不容易想到的值，如666666，當遇到一個666666時就返回true，如果在遍歷過程中一直走到空都再沒有遇到一個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īng)方法）
?就想操場的跑道上，有跑的快的人和跑得慢的人，快的人會不斷追上慢的人。
?設(shè)置雙指針，從head開始走，快指針一次跑兩步，慢指針一次跑一步，鏈表中是有環(huán)的，快指針一定會抓到慢指針。
?在慢指針進環(huán)時，快指針已經(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)一定會相遇。
思考：

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

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

1. m為偶數(shù)

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

---

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

和第一道題不一樣的是這道題如果有環(huán)，就返回入環(huán)的第一個節(jié)點，如果鏈表無環(huán)，就返回NULL。
接下來就要進行分析
?當快指針與慢指針相遇時，快指針所走的路程是慢指針的兩倍。
?假設(shè)起點到入環(huán)口的距離是L，圓環(huán)的長度為C，入口點到相遇點的距離為x，這時通過分析就可以列出一個等式。

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

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

設(shè)置兩個指針，第一個指針從起始位置出發(fā)，另一個指針從相遇點出發(fā)，他們就會在環(huán)的入口處相遇。
套用第一道題的思路，快慢指針相遇時找到相遇點，在設(shè)置兩個指針分別出發(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)形鏈表的約瑟夫問題

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

要注意
看代碼，講解很詳細

#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é)點的前一個}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);//第一個編號為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++)//因為移動三步，是移動量兩次。{hei = hei->next;}LN* pop = hei;//找到要刪除的節(jié)點pophei = hei->next;//更換hei的位置Popnode(hei,pop);//刪除pop。}printf("%d ", hei->val);//打印留下的節(jié)點的數(shù)值。return 0;
}

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