單鏈表的常見操作比較多，而且有些操作比較有技巧，本文就來聊聊這些不容易想到操作。

單鏈表倒數(shù)第 k 個節(jié)點

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

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

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

答案是肯定的，這種解法稱作 雙指針法，它比較巧妙，如果以前沒接觸過過的話，不容易想到，下面就來詳細介紹它。

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

此時，如果 p1 再移動 n - k 步就到達鏈表結(jié)尾的 null 節(jié)點了。

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

最后，指針 p1 和 p2 同時向前移動，直到 p1 到達鏈表結(jié)尾的 null 節(jié)點，此時兩個指針的指向如下圖所示：

當 p1 到達 null 節(jié)點時，p2 走了 n - k 步，也就是倒數(shù)第 k 個節(jié)點。

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

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

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

// 單鏈表節(jié)點結(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 個節(jié)點
ListNode *findFromEnd(ListNode *head, int k)
{
    if(nullptr == head || k <= 0) return nullptr;
    ListNode *p1 = head;
    // p1 指針先移動 k 步
    int step = 0;
    while (step < k && nullptr != p1)
    {
        p1 = p1->next;
        ++step;        
    }
    //p1 移動的步數(shù)小于 k, 表示鏈表長度小于 k
    //因此鏈表不存在倒數(shù)第 k 個節(jié)點
    if (step < k) return nullptr;
    //p1 和 p2 同時移動，直到 p1 到達尾節(jié)點的下一節(jié)點
    ListNode *p2 = head;
    while (nullptr != p1)
    {
        p2 = p2->next;
        p1 = p1->next;
    }
    return p2;
}

單鏈表中點

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

但是這個方法需要先遍歷整個鏈表，然后再從鏈表頭遍歷到鏈表的中間節(jié)點，整個過程共遍歷了 n + n / 2 個節(jié)點。

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

我們讓指針 p1 和 p2 都指向 head 節(jié)點，兩個指針同時向前移動，p1 每次向前走兩步，p2 每次向前走一步，這樣，當 p1達到鏈表尾節(jié)點時，p2 剛好到達鏈表的中間節(jié)點。

在這個過程中，p1 指針每次走兩步，稱為快指針，p2 指針每次走一步，稱為慢指針，所以，這個小技巧叫做 快慢指針。

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

// 單鏈表節(jié)點結(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é)點
ListNode * middleNode(ListNode *head)
{
    if(nullptr == head) return nullptr;
    //快指針和慢指針初始都指向head
    ListNode *pslow = head;
    ListNode *pfast = head;
    while (nullptr != pfast && nullptr != pfast->next)
    {
        //每次快指針走兩步，慢指針走一步
        //當快指針的下一個節(jié)點為 null時
        //表示快指針達到了末尾節(jié)點,此時退出循環(huán)
        pfast = pfast->next->next;
        pslow = pslow->next;
    }
    return pslow;    
}

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

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

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

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

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

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

快慢指針同從頭節(jié)點同時向前移動，在沒有環(huán)的單鏈表中，它們依次達到尾節(jié)點，但對于有環(huán)的鏈表來說，快慢指針最后會一直在環(huán)中移動，永遠停不下來。

由于兩個指針一塊一慢，并且快指針每次比慢指針多走一步，因此，快指針總有一天會追上慢指針，此時它倆就指向同一個節(jié)點，明白了這一點，就有辦法判斷單鏈是否存在表環(huán)了，具體做法如下：

初始時，快慢指針都指向頭節(jié)點，它們同時向前移動，快指針每次走兩步，慢指針每次走一步，當快指針和慢指針相等時，說明鏈表有環(huán)，如果快指針的下一個節(jié)點是 null 節(jié)點，表示鏈表沒有環(huán)。

根據(jù)上面的思路，就可以寫出實現(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)
    {
        //快指針每次走兩步，慢指針每次走一步
        //當快指針的下一個節(jié)點為 null時
        //表示快指針達到了末尾節(jié)點
        pfast = pfast->next->next;
        pslow = pslow->next;
        if (pfast == pslow)
        {
            return true;
        }
    }
    return false;
}

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

我們再深入下，既然解決了鏈表是否有環(huán)的問題，那能不能知道環(huán)的起始節(jié)點呢 ?

比如: 對于下圖中的鏈表來說，環(huán)的起始節(jié)點是 3。

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

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

A 到 B 的距離是 S1。

B 到 C 的距離是 S2。

C 到 B 的距離是 S3。

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

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

慢指針：S1 + S2。

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

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

簡化下上面的等式可以得到:

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

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

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

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

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

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

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

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

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

兩個鏈表是否相交

給你兩個鏈表的頭節(jié)點，如果這兩個鏈表相交，則返回相交的節(jié)點，如果沒相交，返回 null。

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

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

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

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

實際上相當于兩個鏈表連在一起了，具體看下圖：

圖中綠色的節(jié)點是當前鏈表的節(jié)點，藍色的節(jié)點是對方鏈表的節(jié)點，紅色的是遍歷過程中相遇的節(jié)點，也即兩個鏈表相交的節(jié)點，當兩個鏈表沒有相交時，最后p1 和 p2 都指向了空節(jié)點，這也是我們想要的結(jié)果，大家可以自己模擬下這個過程。

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

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

// 單鏈表節(jié)點結(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é)點
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)的一系列操作，有些方法比較有技巧性，一時不太容易想到，需要大家多去體會和練習，假以時日，我相信大家一定能掌握并熟練使用這些套路的