1.限制與要求
- 不允許修改鏈表結(jié)構(gòu)姑原。
- 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)往弓。
2.思考
2.1判斷是否有環(huán)
如果鏈表有環(huán)疏唾，那么在遍歷鏈表時(shí)則會(huì)陷入死循環(huán)，利用這個(gè)特征函似，我們可以設(shè)計(jì)這樣的算法槐脏。
- 使用一個(gè)slow指針，一個(gè)fast指針撇寞。
- slow指針一次往后遍歷以1個(gè)節(jié)點(diǎn)顿天，fast指針一次往后遍歷2個(gè)節(jié)點(diǎn)，一直做這樣的操作蔑担。
- 如果fast指針在遍歷過(guò)程中牌废，遍歷到了NULL節(jié)點(diǎn)說(shuō)明鏈表沒(méi)有環(huán)。
- 否則當(dāng)slow指針和falst指針相同啤握，則說(shuō)明環(huán)有節(jié)點(diǎn)鸟缕。
2.2環(huán)的入口節(jié)點(diǎn)
我們假定鏈表頭到環(huán)入口的距離是len，環(huán)入口到slow和fast交匯點(diǎn)的距離為x排抬，環(huán)的長(zhǎng)度為R懂从。slow和fast第一次交匯時(shí)，設(shè)slow走的長(zhǎng)度為：d = len + x蹲蒲，而fast走的長(zhǎng)度為：2d = len + nR + x番甩，(n >= 1)，從而我們可以得知：2len + 2x = len + nR + x届搁，即len = nR - x缘薛，(n >= 1)窍育，于是我們可以得到這樣的算法。
- 使用一個(gè)cur指針指向鏈表頭節(jié)點(diǎn)宴胧，一個(gè)inter指針指向第一次的交匯點(diǎn)漱抓。
- cur指針和inter指針一起往后遍歷。
- cur指針和inter指針相等時(shí)恕齐，cur和inter指針指向的就是環(huán)的入口節(jié)點(diǎn)辽旋。
inter指針在遍歷過(guò)程中可能多次(n >= 1)經(jīng)過(guò)環(huán)入口節(jié)點(diǎn)，但當(dāng)cur指針第一次達(dá)到入口節(jié)點(diǎn)時(shí)檐迟，inter指針此時(shí)必然也指向入口節(jié)點(diǎn)。
3.代碼實(shí)現(xiàn)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode * detectCycle(ListNode * head) {
if (NULL == head) return NULL;
ListNode * fast = head;
ListNode * slow = head;
while (1)
{
fast = fast->next ? fast->next : NULL;
if (NULL == fast) break;
fast = fast->next ? fast->next : NULL;
if (NULL == fast) break;
slow = slow->next;
if (slow == fast) break;
}
if (NULL == fast) return NULL;
ListNode * cur = head;
ListNode * inter = slow;
while (cur != inter)
{
cur = cur->next;
inter = inter->next;
}
return cur;
}
};
