鏈表的面試題技巧

面試問(wèn)題總結(jié)

無(wú)法高效獲取長(zhǎng)度，無(wú)法根據(jù)偏移快速訪問(wèn)元素，是鏈表的兩個(gè)劣勢(shì)。然而面試的時(shí)候經(jīng)常碰見(jiàn)諸如獲取倒數(shù)第k個(gè)元素，獲取中間位置的元素，判斷鏈表是否存在環(huán)，判斷環(huán)的長(zhǎng)度等和長(zhǎng)度與位置有關(guān)的問(wèn)題。這些問(wèn)題都可以通過(guò)靈活運(yùn)用雙指針來(lái)解決。

Tips：雙指針并不是固定的公式，而是一種思維方式~

先來(lái)看"倒數(shù)第k個(gè)元素的問(wèn)題"。設(shè)有兩個(gè)指針 p 和 q，初始時(shí)均指向頭結(jié)點(diǎn)。首先，先讓 p 沿著 next 移動(dòng) k 次。此時(shí)，p 指向第 k+1個(gè)結(jié)點(diǎn)，q 指向頭節(jié)點(diǎn)，兩個(gè)指針的距離為 k 。然后，同時(shí)移動(dòng) p 和 q，直到 p 指向空，此時(shí) p 即指向倒數(shù)第 k 個(gè)結(jié)點(diǎn)?？梢詤⒖枷聢D來(lái)理解：

移動(dòng)過(guò)程中保持距離為 k

class?Solution?{
public:
????ListNode*?getKthFromEnd(ListNode*?head,?int?k)?{
????????ListNode?*p?=?head,?*q?=?head;?//初始化
????????while(k--)?{???//將?p指針移動(dòng)?k?次
????????????p?=?p->next;
????????}
????????while(p?!=?nullptr)?{//同時(shí)移動(dòng)，直到?p?==?nullptr
????????????p?=?p->next;
????????????q?=?q->next;
????????}
????????return?q;
????}
};

獲取中間元素的問(wèn)題。設(shè)有兩個(gè)指針 fast 和 slow，初始時(shí)指向頭節(jié)點(diǎn)。每次移動(dòng)時(shí)，fast向后走兩次，slow向后走一次，直到 fast 無(wú)法向后走兩次。這使得在每輪移動(dòng)之后。fast 和 slow 的距離就會(huì)增加一。設(shè)鏈表有 n 個(gè)元素，那么最多移動(dòng) n/2 輪。當(dāng) n 為奇數(shù)時(shí)，slow 恰好指向中間結(jié)點(diǎn)，當(dāng) n 為 偶數(shù)時(shí)，slow 恰好指向中間兩個(gè)結(jié)點(diǎn)的靠前一個(gè)(可以考慮下如何使其指向后一個(gè)結(jié)點(diǎn)呢？)。

快慢指針

下述代碼實(shí)現(xiàn)了 n 為偶數(shù)時(shí)慢指針指向靠后結(jié)點(diǎn)。

class?Solution?{
public:
????ListNode*?middleNode(ListNode*?head)?{
????????ListNode?*p?=?head,?*q?=?head;
????????while(q?!=?nullptr?&&?q->next?!=?nullptr)?{
????????????p?=?p->next;
????????????q?=?q->next->next;
????????}
????????return?p;
????}?
};

是否存在環(huán)的問(wèn)題

如果將尾結(jié)點(diǎn)的 next 指針指向其他任意一個(gè)結(jié)點(diǎn)，那么鏈表就存在了一個(gè)環(huán)。

一個(gè)有環(huán)的鏈表

上一部分中，總結(jié)快慢指針的特性 —— 每輪移動(dòng)之后兩者的距離會(huì)加一。下面會(huì)繼續(xù)用該特性解決環(huán)的問(wèn)題。
當(dāng)一個(gè)鏈表有環(huán)時(shí)，快慢指針都會(huì)陷入環(huán)中進(jìn)行無(wú)限次移動(dòng)，然后變成了追及問(wèn)題。想象一下在操場(chǎng)跑步的場(chǎng)景，只要一直跑下去，快的總會(huì)追上慢的。當(dāng)兩個(gè)指針都進(jìn)入環(huán)后，每輪移動(dòng)使得慢指針到快指針的距離增加一，同時(shí)快指針到慢指針的距離也減少一，只要一直移動(dòng)下去，快指針總會(huì)追上慢指針。

快慢指針在環(huán)上追及

根據(jù)上述表述得出，如果一個(gè)鏈表存在環(huán)，那么快慢指針必然會(huì)相遇。實(shí)現(xiàn)代碼如下：

class?Solution?{
public:
????bool?hasCycle(ListNode?*head)?{
????????ListNode?*slow?=?head;
????????ListNode?*fast?=?head;
????????while(fast?!=?nullptr)?{
????????????fast?=?fast->next;
????????????if(fast?!=?nullptr)?{
????????????????fast?=?fast->next;
????????????}
????????????if(fast?==?slow)?{
????????????????return?true;
????????????}
????????????slow?=?slow->next;
????????}
????????return?nullptr;
????}
};

環(huán)的長(zhǎng)度

最后一個(gè)問(wèn)題，如果存在環(huán)，如何判斷環(huán)的長(zhǎng)度呢？方法是，快慢指針相遇后繼續(xù)移動(dòng)，直到第二次相遇。兩次相遇間的移動(dòng)次數(shù)即為環(huán)的長(zhǎng)度。