日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

單鏈表倒數(shù)第 k 個(gè)節(jié)點(diǎn)

單鏈表正向第 k 個(gè)節(jié)點(diǎn)很容易獲得，直接一個(gè) for 循環(huán)遍歷一遍鏈表就能得到，但是如果是逆向第 k 個(gè)節(jié)點(diǎn)，也就是倒數(shù)第 k 個(gè)節(jié)點(diǎn)呢 ?

成都創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、成都網(wǎng)站制作、網(wǎng)站營(yíng)銷(xiāo)推廣、網(wǎng)站開(kāi)發(fā)設(shè)計(jì)，對(duì)服務(wù)成都三輪攪拌車(chē)等多個(gè)行業(yè)擁有豐富的網(wǎng)站建設(shè)及推廣經(jīng)驗(yàn)。成都創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司成立于2013年,提供專(zhuān)業(yè)網(wǎng)站制作報(bào)價(jià)服務(wù),我們深知市場(chǎng)的競(jìng)爭(zhēng)激烈，認(rèn)真對(duì)待每位客戶(hù)，為客戶(hù)提供賞心悅目的作品。 與客戶(hù)共同發(fā)展進(jìn)步，是我們永遠(yuǎn)的責(zé)任！

你也許很快就想到了，逆向第 k 個(gè)節(jié)點(diǎn)相當(dāng)于正向第 n - k 個(gè)節(jié)點(diǎn), 這里的 n 是鏈表長(zhǎng)度，對(duì)于單鏈表來(lái)說(shuō)，需要遍歷一遍鏈表才能計(jì)算出 n 的值，然后再次遍歷 n - k 個(gè)節(jié)點(diǎn), 才最終獲得鏈表倒數(shù)第 k 個(gè)節(jié)點(diǎn)。

上面整個(gè)過(guò)程總共遍歷了 n + n - k 個(gè)節(jié)點(diǎn)，能否只遍歷 n 個(gè)節(jié)點(diǎn)就能得到倒數(shù)第 n 個(gè)節(jié)點(diǎn)呢 ?

答案是肯定的，這種解法稱(chēng)作 雙指針?lè)?，它比較巧妙，如果以前沒(méi)接觸過(guò)過(guò)的話，不容易想到，下面就來(lái)詳細(xì)介紹它。

假如 k = 2, 現(xiàn)在讓指針 p1 指向 head 節(jié)點(diǎn)，然后移動(dòng) k 步，結(jié)果如下圖：

此時(shí)，如果 p1 再移動(dòng) n - k 步就到達(dá)鏈表結(jié)尾的 null 節(jié)點(diǎn)了。

再用一個(gè)指針 p2 指向 head 節(jié)點(diǎn)，指針 p1 和 p2 的指向如下圖所示：

最后，指針 p1 和 p2 同時(shí)向前移動(dòng)，直到 p1 到達(dá)鏈表結(jié)尾的 null 節(jié)點(diǎn)，此時(shí)兩個(gè)指針的指向如下圖所示：

當(dāng) p1 到達(dá) null 節(jié)點(diǎn)時(shí)，p2 走了 n - k 步，也就是倒數(shù)第 k 個(gè)節(jié)點(diǎn)。

這樣，利用 p1 和 p2 兩個(gè)指針，只需要遍歷一遍鏈表就能得到倒數(shù)第 k 個(gè)節(jié)點(diǎn)，也即 p2 指向的節(jié)點(diǎn)。

在整個(gè)過(guò)程中，使用了兩個(gè)指針，所以這個(gè)技巧稱(chēng)作 雙指針?lè)?，很多鏈表相關(guān)的算法題都可以用這個(gè)技巧解決，理解了這個(gè)套路，以后再遇到類(lèi)似的問(wèn)題就可以手到擒來(lái)了。

好了，流程講完了，下面給出完整代碼供大家參考：

// 單鏈表節(jié)點(diǎn)結(jié)構(gòu)
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *pnext) : val(x), next(pnext) {}
};
// 返回單鏈表倒數(shù)第 k 個(gè)節(jié)點(diǎn)
ListNode *findFromEnd(ListNode *head, int k)
{
    if(nullptr == head || k <= 0) return nullptr;
    ListNode *p1 = head;
    // p1 指針先移動(dòng) k 步
    int step = 0;
    while (step < k && nullptr != p1)
    {
        p1 = p1->next;
        ++step;        
    }
    //p1 移動(dòng)的步數(shù)小于 k, 表示鏈表長(zhǎng)度小于 k
    //因此鏈表不存在倒數(shù)第 k 個(gè)節(jié)點(diǎn)
    if (step < k) return nullptr;
    //p1 和 p2 同時(shí)移動(dòng)，直到 p1 到達(dá)尾節(jié)點(diǎn)的下一節(jié)點(diǎn)
    ListNode *p2 = head;
    while (nullptr != p1)
    {
        p2 = p2->next;
        p1 = p1->next;
    }
    return p2;
}

單鏈表中點(diǎn)

想得到單鏈表的中點(diǎn)，首先想到的是先得到鏈表的長(zhǎng)度 n，然后從鏈頭開(kāi)始往前走，每走一步，計(jì)數(shù)就加一，直到計(jì)數(shù)達(dá)到鏈表長(zhǎng)度的一半兒 n / 2，此時(shí)所在的節(jié)點(diǎn)即為鏈表的中點(diǎn)了。

但是這個(gè)方法需要先遍歷整個(gè)鏈表，然后再?gòu)逆湵眍^遍歷到鏈表的中間節(jié)點(diǎn)，整個(gè)過(guò)程共遍歷了 n + n / 2 個(gè)節(jié)點(diǎn)。

這里介紹一種方法，只需要遍歷 n 個(gè)節(jié)點(diǎn)就可以得到鏈表的中間節(jié)點(diǎn)。

我們讓指針 p1 和 p2 都指向 head 節(jié)點(diǎn)，兩個(gè)指針同時(shí)向前移動(dòng)，p1 每次向前走兩步，p2 每次向前走一步，這樣，當(dāng) p1達(dá)到鏈表尾節(jié)點(diǎn)時(shí)，p2 剛好到達(dá)鏈表的中間節(jié)點(diǎn)。

在這個(gè)過(guò)程中，p1 指針每次走兩步，稱(chēng)為快指針，p2 指針每次走一步，稱(chēng)為慢指針，所以，這個(gè)小技巧叫做 快慢指針。

根據(jù)上面的思路，我們就可以寫(xiě)出算法的實(shí)現(xiàn)代碼了。

// 單鏈表節(jié)點(diǎn)結(jié)構(gòu)
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *pnext) : val(x), next(pnext) {}
};
// 返回單鏈表中間節(jié)點(diǎn)
ListNode * middleNode(ListNode *head)
{
    if(nullptr == head) return nullptr;
    //快指針和慢指針初始都指向head
    ListNode *pslow = head;
    ListNode *pfast = head;
    while (nullptr != pfast && nullptr != pfast->next)
    {
        //每次快指針走兩步，慢指針走一步
        //當(dāng)快指針的下一個(gè)節(jié)點(diǎn)為 null時(shí)
        //表示快指針達(dá)到了末尾節(jié)點(diǎn),此時(shí)退出循環(huán)
        pfast = pfast->next->next;
        pslow = pslow->next;
    }
    return pslow;    
}

需要說(shuō)明一點(diǎn)，如果單鏈表長(zhǎng)度為偶數(shù)，也就是中間節(jié)點(diǎn)有兩個(gè)，上面的解法返回的是靠后一個(gè)節(jié)點(diǎn)。

例如: 單鏈表 1 -> 2 -> 3 -> 4 -> 5 -> 6，長(zhǎng)度為 6，它的中間節(jié)點(diǎn)是 3 和 4，那么，用上面的解法得到的中間節(jié)點(diǎn)是 4 而不是 3。

鏈表是否包含環(huán)

如下圖所示，圖中是一個(gè)長(zhǎng)度為5的鏈表，最后一個(gè)節(jié)點(diǎn)指向了第三個(gè)節(jié)點(diǎn)，構(gòu)成了一個(gè)環(huán)。

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

如何判斷單鏈表存在環(huán)呢 ?我們可以借用 單鏈表的中點(diǎn) 問(wèn)題的思路。

快慢指針同從頭節(jié)點(diǎn)同時(shí)向前移動(dòng)，在沒(méi)有環(huán)的單鏈表中，它們依次達(dá)到尾節(jié)點(diǎn)，但對(duì)于有環(huán)的鏈表來(lái)說(shuō)，快慢指針最后會(huì)一直在環(huán)中移動(dòng)，永遠(yuǎn)停不下來(lái)。

由于兩個(gè)指針一塊一慢，并且快指針每次比慢指針多走一步，因此，快指針總有一天會(huì)追上慢指針，此時(shí)它倆就指向同一個(gè)節(jié)點(diǎn)，明白了這一點(diǎn)，就有辦法判斷單鏈?zhǔn)欠翊嬖诒憝h(huán)了，具體做法如下：

初始時(shí)，快慢指針都指向頭節(jié)點(diǎn)，它們同時(shí)向前移動(dòng)，快指針每次走兩步，慢指針每次走一步，當(dāng)快指針和慢指針相等時(shí)，說(shuō)明鏈表有環(huán)，如果快指針的下一個(gè)節(jié)點(diǎn)是 null 節(jié)點(diǎn)，表示鏈表沒(méi)有環(huán)。

根據(jù)上面的思路，就可以寫(xiě)出實(shí)現(xiàn)代碼了。

//返回單鏈表是否存在環(huán)
bool hasCycle(ListNode *head)
{
    if(nullptr == head) return false;
    //快指針和慢指針初始都指向head
    ListNode *pslow = head;
    ListNode *pfast = head;
    while (nullptr != pfast && nullptr != pfast->next)
    {
        //快指針每次走兩步，慢指針每次走一步
        //當(dāng)快指針的下一個(gè)節(jié)點(diǎn)為 null時(shí)
        //表示快指針達(dá)到了末尾節(jié)點(diǎn)
        pfast = pfast->next->next;
        pslow = pslow->next;
        if (pfast == pslow)
        {
            return true;
        }
    }
    return false;
}

鏈表環(huán)的起始節(jié)點(diǎn)

我們?cè)偕钊胂?，既然解決了鏈表是否有環(huán)的問(wèn)題，那能不能知道環(huán)的起始節(jié)點(diǎn)呢 ?

比如: 對(duì)于下圖中的鏈表來(lái)說(shuō)，環(huán)的起始節(jié)點(diǎn)是 3。

解決的方法依然是使用快慢指針，快指針每次走兩步，慢指針每次走一步。

下圖是一個(gè)簡(jiǎn)易的環(huán)形鏈表圖，其中 A 為鏈表頭節(jié)點(diǎn)，B 為環(huán)的起始節(jié)點(diǎn)，C為 快指針和慢指針在環(huán)中相遇的節(jié)點(diǎn)(至于快指針和慢指針為什么一定會(huì)在環(huán)中相遇，在上一小節(jié)有解釋?zhuān)@里不在贅述了)。

A 到 B 的距離是 S1。

B 到 C 的距離是 S2。

C 到 B 的距離是 S3。

假設(shè)，當(dāng)快指針和慢指針在 C點(diǎn)相遇時(shí)，快指針已經(jīng)繞著環(huán)走了 n 圈，則相遇時(shí)各自走過(guò)的路程如下：

快指針: S1 + n * ( S2 + S3 ) + S2。

慢指針：S1 + S2。

由于快指針走過(guò)的路程是慢指針的 2 倍，則有：

S1 + n * ( S2 + S3 ) = 2 * (S1 + S2)

簡(jiǎn)化下上面的等式可以得到:

S1 = (n - 1) * (S2 + S3) + S3

S2 + S3 剛好是環(huán)的長(zhǎng)度，所以，上面的結(jié)果可以理解為，從 A 到 B 的距離，等于從相遇點(diǎn) C 出發(fā)，繞著環(huán)走 n - 1圈 ( 此時(shí)會(huì)回到 C 點(diǎn) ) ，然后再走 S3 就到達(dá)了 B 點(diǎn)，也即環(huán)的起始點(diǎn)。

因此，當(dāng)快慢指針相遇后，再額外使用一個(gè)指針指向鏈表頭節(jié)點(diǎn)，然后這個(gè)額外指針和慢指針同時(shí)移動(dòng)，它們最終一定會(huì)在環(huán)的起始節(jié)點(diǎn)相遇。

搞明白了上面的推理過(guò)程之后，實(shí)現(xiàn)代碼直接在 鏈表是否存在環(huán) 那一小節(jié)的基礎(chǔ)上稍作修改即可，具體的代碼如下：

//返回單鏈表環(huán)的起始節(jié)點(diǎn)
ListNode *entrynodeInLoop(ListNode *head)
{
    if (nullptr == head || nullptr == head->next)
        return nullptr;
    ListNode *pslow = head;  //慢指針
    ListNode *pfast = head;  //快指針
    ListNode *ppoint = nullptr;//指向快慢指針相遇時(shí)的節(jié)點(diǎn)
    while (nullptr != pfast && nullptr != pfast->next)
    {
        pslow = pslow->next;
        pfast = pfast->next->next;
        if (pslow == pfast)
        {
            ppoint = pslow;
            break;
        }
    }
    //相遇節(jié)點(diǎn)為null,表示沒(méi)有環(huán)
    if (nullptr == ppoint) return nullptr;
    pslow = head;  //慢指針指向頭節(jié)點(diǎn)
    while (pslow != ppoint)
    {
        pslow = pslow->next;
        ppoint = ppoint->next;
    }
    return ppoint;
}

其實(shí)，鏈表是否有環(huán) 以及 鏈表環(huán)的起始節(jié)點(diǎn) 還有一種比較直觀的求解方法。

額外增加一個(gè)記錄節(jié)點(diǎn)指針的集合，然后從頭節(jié)點(diǎn)開(kāi)始往前遍歷，每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)，查詢(xún)集合中是否已存在該節(jié)點(diǎn)，如果不存在，節(jié)點(diǎn)指針加入到集合中，如果存在，則表示該節(jié)點(diǎn)就是環(huán)的入口節(jié)點(diǎn)。

這種方法比較好理解，但是它的空間復(fù)雜度是 O(N), 時(shí)間復(fù)雜度跟 快慢指針 相同，這里也給出實(shí)現(xiàn)代碼供參考。

//返回鏈表環(huán)的起始節(jié)點(diǎn)
ListNode *entrynodeInLoop(ListNode *head)
{
    if(nullptr == head) return nullptr;
    //鏈表節(jié)點(diǎn)的集合
    unordered_set setnode;
    ListNode *p = head;
    while (nullptr != p)
    {
        auto iter = setnode.find(p);
        if( iter != setnode.end())
        {
            //集合中找到了相同的節(jié)點(diǎn)
            //此節(jié)點(diǎn)即為環(huán)的入口
            return p;
        }
        //節(jié)點(diǎn)不在集合中，則加入集合
        setnode.insert(p);
        //移動(dòng)到下一個(gè)節(jié)點(diǎn)
        p = p->next;
    }
    //不存在環(huán)，返回 nullptr
    return nullptr;    
}

兩個(gè)鏈表是否相交

給你兩個(gè)鏈表的頭節(jié)點(diǎn)，如果這兩個(gè)鏈表相交，則返回相交的節(jié)點(diǎn)，如果沒(méi)相交，返回 null。

比如下圖中，兩個(gè)鏈表相交的節(jié)點(diǎn)是 3。

初看這個(gè)問(wèn)題，最容易想到的方法是分別遍歷兩個(gè)鏈表，用一個(gè)集合記錄遍歷過(guò)程中的節(jié)點(diǎn)，如果存在相交的節(jié)點(diǎn)，肯定會(huì)多次訪問(wèn)該節(jié)點(diǎn)，當(dāng)?shù)诙卧L問(wèn)該節(jié)點(diǎn)的時(shí)候，集合中已經(jīng)存在該節(jié)點(diǎn)了，如果沒(méi)有相交，則集合中不會(huì)出現(xiàn)兩個(gè)相同的節(jié)點(diǎn)。

但利用集合臨時(shí)存儲(chǔ)遍歷過(guò)的節(jié)點(diǎn)的方法，空間復(fù)雜度是 O(N)，如何在 O(1) 的空間復(fù)雜度內(nèi)解決呢?

解決方法是利用兩個(gè)指針p1 和 p2，初始時(shí) p1 指向第一個(gè)鏈表的頭節(jié)點(diǎn)，p2指向第二個(gè)鏈表的頭節(jié)點(diǎn)，然后同時(shí)開(kāi)始遍歷鏈表，p1 遍歷完鏈表之后，指向第二個(gè)鏈表的頭節(jié)點(diǎn)，p2 遍歷完鏈表之后，指向第一個(gè)鏈表的頭節(jié)點(diǎn)。

實(shí)際上相當(dāng)于兩個(gè)鏈表連在一起了，具體看下圖：

圖中綠色的節(jié)點(diǎn)是當(dāng)前鏈表的節(jié)點(diǎn)，藍(lán)色的節(jié)點(diǎn)是對(duì)方鏈表的節(jié)點(diǎn)，紅色的是遍歷過(guò)程中相遇的節(jié)點(diǎn)，也即兩個(gè)鏈表相交的節(jié)點(diǎn)，當(dāng)兩個(gè)鏈表沒(méi)有相交時(shí)，最后p1 和 p2 都指向了空節(jié)點(diǎn)，這也是我們想要的結(jié)果，大家可以自己模擬下這個(gè)過(guò)程。

因此，此題的關(guān)鍵是找到一種辦法，使得 p1 和 p2 能同時(shí)到達(dá)兩個(gè)鏈表相交的節(jié)點(diǎn)。

根據(jù)上述的方法，可以寫(xiě)出實(shí)現(xiàn)代碼 :

// 單鏈表節(jié)點(diǎn)結(jié)構(gòu)
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *pnext) : val(x), next(pnext) {}
};
//返回兩個(gè)鏈表相交的節(jié)點(diǎn)
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    if (nullptr == headA || nullptr == headB)
        return nullptr;
    ListNode *pa = headA;
    ListNode *pb = headB;
    while (pa != pb)
    {
        pa = (nullptr != pa) ? pa->next : headB;
        pb = (nullptr != pb) ? pb->next : headA;
    }
    return pa;
}

小結(jié)

本文講解了鏈表相關(guān)的一系列操作，有些方法比較有技巧性，一時(shí)不太容易想到，需要大家多去體會(huì)和練習(xí)，假以時(shí)日，我相信大家一定能掌握并熟練使用這些套路的

網(wǎng)站欄目：一文弄清楚鏈表技巧
標(biāo)題URL：http://m.5511xx.com/article/cdchhco.html