C++鏈表求環(huán)

已知鏈表中可能存在環(huán)，若有環(huán)返回環(huán)起始節(jié)點，否則返回NULL。

勐海網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián),勐海網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為勐海近1000家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站建設(shè)要多少錢，請找那個售后服務(wù)好的勐海做網(wǎng)站的公司定做！

//方法一，使用set求環(huán)起始節(jié)點。

//遍歷鏈表，將鏈表中節(jié)點對應(yīng)的指針(地址)插入set。 在遍歷時插入節(jié)點前，需

//要在set中查找，第一個在set中發(fā)現(xiàn)的的節(jié)點地址XM代理申請，即是鏈表環(huán)的起點。

//Runtime: 24 ms，Memory Usage: 12 MB。

class Solution

{

public:

Solution(){}

~Solution(){}

ListNode detectCycle(ListNode head)

{

std::set node_set;

while (head)

{

if (node_set.find(head)!=node_set.end())

{

return head;

}

node_set.insert(head);

head = head->next;

}

return NULL;

}

};

/*

//方法二：快慢指針。Runtime: 12 ms，Memory Usage: 9.9 MB。

//時間復(fù)雜度為O(n)

class Solution

{

public:

Solution(){}

~Solution(){}

ListNode detectCycle(ListNode head)

{

ListNode* fast = head;

ListNode* slow = head;

ListNode* meet = NULL;

while (fast)

{

slow = slow->next;

fast = fast->next;

if (!fast)

{

return NULL;

}

fast = fast->next;

if (fast==slow)

{

meet = fast;

break;

}

}

if (meet==NULL)

{

return NULL;

}

while (head&&meet)

{

if (head==meet)

{

return head;

}

head = head->next;

meet = meet->next;

}

return NULL;

}

};

*/

int main()

{

ListNode a(12);

ListNode b(34);

ListNode c(31);

ListNode d(41);

ListNode e(51);

ListNode f(61);

ListNode g(71);

a.next = &b;

b.next = &c;

c.next = &d;

d.next = &e;

e.next = &f;

f.next = &g;

g.next =&c;

Solution solve;

ListNode* node = solve.detectCycle(&a);

if (node)

{

printf("%d\n",node->val);

}

else

{

printf("NULL\n");

}

return 0;

}

網(wǎng)站標(biāo)題：C++鏈表求環(huán)
分享網(wǎng)址：http://bm7419.com/article12/jcsedc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營銷型網(wǎng)站建設(shè)、搜索引擎優(yōu)化、網(wǎng)站設(shè)計、App設(shè)計、網(wǎng)站維護(hù)、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)