目錄

一、相交鏈表

二、環(huán)形鏈表

三、環(huán)形鏈表 ||

---

---

一、相交鏈表

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表不存在相交節(jié)點(diǎn)，返回 null 。

圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：

?題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。

代碼實(shí)現(xiàn)：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{// 1. 分別找到兩個(gè)單鏈表的尾結(jié)點(diǎn)，并計(jì)算它們的長度struct ListNode *tailA = headA, *tailB = headB;int lenA = 1, lenB = 1;while (tailA->next != NULL){++lenA;tailA = tailA->next;}while (tailB->next != NULL){++lenB;tailB = tailB->next;}if (tailA != tailB) ?// 如果兩個(gè)鏈表不相交，則尾結(jié)點(diǎn)的地址不同{return NULL;}// 2. 讓指向長鏈表的指針先走差距步int gap = abs(lenA - lenB);struct ListNode *longCur = headA, *shortCur = headB;if (lenA < lenB){longCur = headB;shortCur = headA;}for (int i = 0; i < gap; ++i){longCur = longCur->next;}// 3. 讓 longCur 和 shortCur 同時(shí)向后走，直到找到相同地址的結(jié)點(diǎn)while (longCur != shortCur){longCur = longCur->next;shortCur = shortCur->next;}return longCur;
}

---

二、環(huán)形鏈表

給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，判斷鏈表中是否有環(huán)。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數(shù)進(jìn)行傳遞 。僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

示例 1：

?輸入：head = [3,2,0,-4], pos = 1

輸出：true

解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

示例 2：

?輸入：head = [1,2], pos = 0

輸出：true

解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。

示例 3：

?輸入：head = [1], pos = -1

輸出：false

解釋：鏈表中沒有環(huán)。

提示：

• 鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [0, 10^4]

• -105 <= Node.val <= 105

• pos 為 -1 或者鏈表中的一個(gè) 有效索引 。

進(jìn)階：你能用 O(1)（即，常量）內(nèi)存解決此問題嗎？

代碼實(shí)現(xiàn)一：

bool hasCycle(struct ListNode *head) 
{struct ListNode* addr[10000] = { 0 }; ?// addr 是保存每個(gè)結(jié)點(diǎn)地址的指針數(shù)組int pos = 0; ?// pos 始終是第一個(gè)未存放結(jié)點(diǎn)地址的數(shù)組下標(biāo)struct ListNode* cur = head;while (cur != NULL){addr[pos++] = cur;// 檢查 cur->next 是否指向之前的結(jié)點(diǎn)或自己for (int i = 0; i < pos; ++i) {if (addr[i] == cur->next){return true;}}cur = cur->next;}return false; ?
}

代碼實(shí)現(xiàn)二（快慢雙指針）：

bool hasCycle(struct ListNode *head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next) ?// 如果鏈表不帶環(huán)，則快指針先走到空或尾{slow = slow->next;fast = fast->next->next;if (slow == fast){return true;}}return false;
}

問題（前提是鏈表帶環(huán)）：

1. 快慢指針從相同的起始位置出發(fā)，慢指針 slow 每次走一步，快指針 fast 每次走兩步，請(qǐng)問這兩個(gè)指針為什么一定會(huì)再次相遇？

   設(shè)當(dāng) slow 走到入環(huán)的第一個(gè)結(jié)點(diǎn)時(shí)，fast 距 slow y 步（0 <= y <= C，C 表示環(huán)的長度），然后 slow 走 x 步，fast 走 2x 步后，兩個(gè)指針再次相遇，則有：2x - x = y，即 x = y。

   y == 0，即當(dāng) slow 走到入環(huán)的第一個(gè)結(jié)點(diǎn)時(shí)，就和 fast 再次相遇了；y == C，即入環(huán)的第一個(gè)結(jié)點(diǎn)就是頭結(jié)點(diǎn)，如示例 2。

2. 快慢指針從相同的起始位置出發(fā)，慢指針 slow 每次走一步，快指針 fast 每次走 n 步（n >= 3），請(qǐng)問這兩個(gè)指針也一定會(huì)再次相遇嗎？

   n * x - x = y，即 (n - 1)x = y ==> x = y / (n - 1)。

   例如：

   

   ?

---

三、環(huán)形鏈表 ||

給定一個(gè)鏈表的頭節(jié)點(diǎn) head ，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。

不允許修改 鏈表。

示例 1：

?輸入：head = [3,2,0,-4], pos = 1

輸出：返回索引為 1 的鏈表節(jié)點(diǎn)

解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

示例 2：

?輸入：head = [1,2], pos = 0

輸出：返回索引為 0 的鏈表節(jié)點(diǎn)

解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。

示例 3：

?輸入：head = [1], pos = -1

輸出：返回 null

解釋：鏈表中沒有環(huán)。

提示：

• 鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍 [0, 10^4] 內(nèi)

• -105 <= Node.val <= 105

• pos 的值為 -1 或者鏈表中的一個(gè)有效索引

進(jìn)階：你是否可以使用 O(1) 空間解決此題？

代碼實(shí)現(xiàn)一：

struct ListNode *detectCycle(struct ListNode *head) 
{struct ListNode* addr[10000] = { 0 };int pos = 0;struct ListNode* cur = head;while (cur != NULL){addr[pos++] = cur;for (int i = 0; i < pos; ++i){if (addr[i] == cur->next){return addr[i];}}cur = cur->next;} ?return NULL;
}

代碼實(shí)現(xiàn)二：

struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast) ?// 再次相遇{struct ListNode* start = head; ?// start 從起始結(jié)點(diǎn)出發(fā)struct ListNode* meet = slow; ?// meet 從相遇結(jié)點(diǎn)出發(fā)while (start != meet){start = start->next;meet = meet->next;}return start; ?// 或者 return meet;}}return NULL;
}

分析：

其中 L 表示指針從頭結(jié)點(diǎn)走到入環(huán)第一個(gè)結(jié)點(diǎn)所需要的步數(shù)，x 表示慢指針走到入環(huán)的第一個(gè)結(jié)點(diǎn)后，與快指針再次相遇所需走的步數(shù)，C 則表示環(huán)的長度。

從起點(diǎn)出發(fā)到再次相遇，慢指針 slow 走的步數(shù)為 L + x，快指針 fast 走的步數(shù)為 L + k * C + x（k >= 1），又因?yàn)?slow 每次走一步，fast 每次走兩步，所以有：2(L + x) = L + k * C + x，即 L = k * C + x ==> L = (k - 1)C + x。

由此得出一個(gè)結(jié)論：在鏈表有環(huán)的前提下，一個(gè)指針從起始結(jié)點(diǎn)開始走，另一個(gè)指針從再相遇結(jié)點(diǎn)開始走，兩個(gè)指針每次走一步，最終這兩個(gè)結(jié)點(diǎn)會(huì)在入環(huán)的第一個(gè)結(jié)點(diǎn)相遇。

代碼實(shí)現(xiàn)三：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode *tailA = headA, *tailB = headB;int lenA = 1, lenB = 1;while (tailA->next != NULL){++lenA;tailA = tailA->next;}while (tailB->next != NULL){++lenB;tailB = tailB->next;}if (tailA != tailB){return NULL;}int gap = abs(lenA - lenB);struct ListNode *longCur = headA, *shortCur = headB;if (lenA < lenB){longCur = headB;shortCur = headA;}for (int i = 0; i < gap; ++i){longCur = longCur->next;}while (longCur != shortCur){longCur = longCur->next;shortCur = shortCur->next;}return longCur;
}
?
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){// 轉(zhuǎn)換成求相交結(jié)點(diǎn)struct ListNode* headB = slow->next;slow->next = NULL;return getIntersectionNode(head, headB);}}return NULL;
}