劍指offer 連結串列中環的入口結點

2022-11-24 15:01:43 字數 1259 閱讀 3411

給一個連結串列,若其中包含環,請找出該連結串列的環的入口結點,否則,輸出null。

題目分析:

1)先判斷是否有環。

快慢指標,同時從表頭出發,一個每次走一步,另一個走兩步。快慢指標能相遇,則說明有環,同時記錄相遇的節點指標,否則直接返回null

2)我們知道快慢指標相遇的地方在環內,那麼,我們以相遇的節點為起始,用另外一個指標遍歷,當下一次再遇到這個相遇的節點,便知道環的節點數。因為是單連結串列,所以環的位置必然在最後,相當於我們要找的就是連結串列的倒數第k(環的節點個數)個節點。

1/*2

struct listnode 8};

9*/10class

solution

16 listnode *slow =phead;

17bool flag = false;18

if (slow->next ==nullptr)

21 listnode *fast = slow->next;

22 listnode *meeting =nullptr;

23while (fast !=nullptr)

29 slow = slow->next;

30 fast = fast->next;

31if (fast !=nullptr) 34}

35if (flag == true

) else40}

41public

:42 listnode* entrynodeofloop(listnode*phead)

4348

//得到環中節點的數目

49int nodesinloop = 1

;50 listnode *pnode1 =meetingnode;

51while (pnode1->next !=meetingnode)

55//

先移動pnode1, 次數為環中節點的數目

56 pnode1 =phead;

57for (int i = 0; i < nodesinloop; i++)

60//

再同時移動pnode1和pnode2

61 listnode *pnode2 =phead;

62while (pnode1 !=pnode2)

66return

pnode1;67}

68 };

劍指offer 55 連結串列中環的入口結點

給一個連結串列,若其中包含環,請找出該連結串列的環的入口結點,否則,輸出null。思路 用兩個指標代表一快一慢的指標,快指標一次前進2個單位,慢指標一次前進1個單位。兩個指標同時出發。慢指標前進了x個單位,快指標前進了2x個單位。則有 2x n x 推匯出 n x。則慢指標走了一個環的步數,快指標走...

python劍指offer 連結串列中環的入口節點

題目 一個連結串列中包含環,請找出該連結串列的環的入口結點。思路 先說個定理 兩個指標一個fast 一個slow同時從一個連結串列的頭部出發,fast一次走2步,slow一次走一步,如果該連結串列有環,兩個指標必然在環內相遇,此時只需要把其中的一個指標重新指向連結串列頭部,另一個不變 還在環內 這次...

劍指offer系列44 連結串列中環的入口結點

這個題要找到連結串列中的環的入口,很自然的可以分為兩個問題。首先是判斷連結串列中是否有環,其次尋找到環的入口。1.判斷是否有環,這裡有兩個指標。一個一次走一步,一個一次走兩步。用這兩個指標在連結串列上走,如果存在環兩個指標一定會相遇,並且相遇的點是在環內。這個很重要,判斷連結串列是否存在環。2.尋找...