软件开发平台及语言笔记大全(超详细)

面試精選：鏈表問題集錦

鏈表問題在面試過程中也是很重要也很基礎的一部分，鏈表本身很靈活，很考查編程功底，所以是很值得考的地方。我將複習過程中覺得比較好的鏈表問題整理了下。

下面是本文所要用到鏈表節點的定義：

struct Node{
    int data;
    Node* next;
};

##1. 在O(1)時間刪除鏈表節點 ###題目描述：給定鏈表的頭指針和一個節點指針，在O(1)時間刪除該節點。[Google面試題]

###分析：本題與《編程之美》上的「從無頭單鏈表中刪除節點」類似。主要思想都是「狸貓換太子」，即用下一個節點數據覆蓋要刪除的節點，然後刪除下一個節點。但是如果節點是尾節點時，該方法就行不通了。

代碼如下：

//O(1)時間刪除鏈表節點，從無頭單鏈表中刪除節點
void deleteRandomNode(Node *cur)
{
    assert(cur != NULL);
    assert(cur->next != NULL);    //不能是尾節點
    Node* pNext = cur->next;
    cur->data = pNext->data;
    cur->next = pNext->next;
    delete pNext;
}

2. 單鏈表的轉置

###題目描述：輸入一個單向鏈表，輸出逆序反轉後的鏈表

###分析：鏈表的轉置是一個很常見、很基礎的數據結構題了，非遞歸的算法很簡單，用三個臨時指針 pre、head、next 在鏈表上循環一遍即可。遞歸算法也是比較簡單的，但是如果思路不清晰估計一時半會兒也寫不出來吧。

下面是循環版本和遞歸版本的鏈表轉置代碼：

//單鏈表的轉置,循環方法
Node* reverseByLoop(Node *head)
{
    if(head == NULL || head->next == NULL)
        return head;
    Node *pre = NULL;
    Node *next = NULL;
    while(head != NULL)
    {
        next = head->next;

        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

//單鏈表的轉置,遞歸方法
Node* reverseByRecursion(Node *head)
{
    //第一個條件是判斷異常，第二個條件是結束判斷
    if(head == NULL || head->next == NULL) 
        return head;

    Node *newHead = reverseByRecursion(head->next);

    head->next->next = head;
    head->next = NULL;

    return newHead;    //返回新鏈表的頭指針
}

##3. 求鏈表倒數第k個節點 ###題目描述：輸入一個單向鏈表，輸出該鏈表中倒數第k個節點，鏈表的倒數第0個節點為鏈表的尾指針。

###分析：設置兩個指針 p1、p2，首先 p1 和 p2 都指向 head，然後 p2 向前走 k 步，這樣 p1 和 p2 之間就間隔 k 個節點，最後 p1 和 p2 同時向前移動，直至 p2 走到鏈表末尾。

代碼如下：

//倒數第k個節點
Node* theKthNode(Node *head,int k)
{
    if(k < 0) return NULL;    //異常判斷

    Node *slow,*fast;
    slow = fast = head;
    int i = k;
    for(;i>0 && fast!=NULL;i--)
    {
        fast = fast->next;
    }

    if(i > 0)    return NULL;    //考慮k大於鏈表長度的case

    while(fast != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

##4. 求鏈表的中間節點 ###題目描述：求鏈表的中間節點，如果鏈表的長度為偶數，返回中間兩個節點的任意一個，若為奇數，則返回中間節點。

###分析：此題的解決思路和第3題「求鏈表的倒數第 k 個節點」很相似。可以先求鏈表的長度，然後計算出中間節點所在鏈表順序的位置。但是如果要求只能掃瞄一遍鏈表，如何解決呢？最高效的解法和第3題一樣，通過兩個指針來完成。用兩個指針從鏈表頭節點開始，一個指針每次向後移動兩步，一個每次移動一步，直到快指針移到到尾節點，那麼慢指針即是所求。

代碼如下：

//求鏈表的中間節點
Node* theMiddleNode(Node *head)
{
    if(head == NULL)
        return NULL;
    Node *slow,*fast;
    slow = fast = head;
    //如果要求在鏈表長度為偶數的情況下，返回中間兩個節點的第一個，可以用下面的循環條件
    //while(fast && fast->next != NULL && fast->next->next != NULL)  
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

##5. 判斷單鏈表是否存在環 ###題目描述：輸入一個單向鏈表，判斷鏈表是否有環？

###分析：通過兩個指針，分別從鏈表的頭節點出發，一個每次向後移動一步，另一個移動兩步，兩個指針移動速度不一樣，如果存在環，那麼兩個指針一定會在環裡相遇。

代碼如下：

//判斷單鏈表是否存在環,參數circleNode是環內節點，後面的題目會用到
bool hasCircle(Node *head,Node *&circleNode)
{
    Node *slow,*fast;
    slow = fast = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            circleNode = fast;
            return true;
        }
    }

    return false;
}

##6. 找到環的入口點 ###題目描述：輸入一個單向鏈表，判斷鏈表是否有環。如果鏈表存在環，如何找到環的入口點？

###解題思路：由上題可知，按照 p2 每次兩步，p1 每次一步的方式走，發現 p2 和 p1 重合，確定了單向鏈表有環路了。接下來，讓p2回到鏈表的頭部，重新走，每次步長不是走2了，而是走1，那麼當 p1 和 p2 再次相遇的時候，就是環路的入口了。

為什麼？：假定起點到環入口點的距離為 a，p1 和 p2 的相交點M與環入口點的距離為b，環路的周長為L，當 p1 和 p2 第一次相遇的時候，假定 p1 走了 n 步。那麼有：

p1走的路徑： a+b ＝ n； p2走的路徑： a+b+kL = 2n； p2 比 p1 多走了k圈環路，總路程是p1的2倍

根據上述公式可以得到 k*L=a+b=n顯然，如果從相遇點M開始，p1 再走 n 步的話，還可以再回到相遇點，同時p2從頭開始走的話，經過n步，也會達到相遇點M。

顯然在這個步驟當中 p1 和 p2 只有前 a 步走的路徑不同，所以當 p1 和 p2 再次重合的時候，必然是在鏈表的環路入口點上。

代碼如下：

//找到環的入口點
Node* findLoopPort(Node *head)
{
    //如果head為空，或者為單結點，則不存在環
    if(head == NULL || head->next == NULL) return NULL;

    Node *slow,*fast;
    slow = fast = head;

    //先判斷是否存在環
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            break;
    }

    if(fast != slow) return NULL;    //不存在環

    fast = head;                //快指針從頭開始走，步長變為1
    while(fast != slow)            //兩者相遇即為入口點
    {
        fast = fast->next;
        slow = slow->next;
    }

    return fast;
}

##7. 編程判斷兩個鏈表是否相交題目描述：給出兩個單向鏈表的頭指針（如下圖所示），

比如h1、h2，判斷這兩個鏈表是否相交。這裡為了簡化問題，我們假設兩個鏈表均不帶環。

##解題思路：

直接循環判斷第一個鏈表的每個節點是否在第二個鏈表中。但，這種方法的時間複雜度為O(Length(h1) * Length(h2))。顯然，我們得找到一種更為有效的方法，至少不能是O（N^2）的複雜度。

針對第一個鏈表直接構造hash表，然後查詢hash表，判斷第二個鏈表的每個節點是否在hash表出現，如果所有的第二個鏈表的節點都能在hash表中找到，即說明第二個鏈表與第一個鏈表有相同的節點。時間複雜度為為線性：O(Length(h1) + Length(h2))，同時為了存儲第一個鏈表的所有節點，空間複雜度為O(Length(h1))。是否還有更好的方法呢，既能夠以線性時間複雜度解決問題，又能減少存儲空間？

轉換為環的問題。把第二個鏈表接在第一個鏈表後面，如果得到的鏈表有環，則說明兩個鏈表相交。如何判斷有環的問題上面已經討論過了，但這裡有更簡單的方法。因為如果有環，則第二個鏈表的表頭一定也在環上，即第二個鏈表會構成一個循環鏈表，我們只需要遍歷第二個鏈表，看是否會回到起始點就可以判斷出來。這個方法的時間複雜度是線性的，空間是常熟。

進一步考慮「如果兩個沒有環的鏈表相交於某一節點，那麼在這個節點之後的所有節點都是兩個鏈表共有的」這個特點，我們可以知道，如果它們相交，則最後一個節點一定是共有的。而我們很容易能得到鏈表的最後一個節點，所以這成了我們簡化解法的一個主要突破口。那麼，我們只要判斷兩個鏈表的尾指針是否相等。相等，則鏈表相交；否則，鏈表不相交。所以，先遍歷第一個鏈表，記住最後一個節點。然後遍歷第二個鏈表，到最後一個節點時和第一個鏈表的最後一個節點做比較，如果相同，則相交，否則，不相交。這樣我們就得到了一個時間複雜度，它為O((Length(h1) + Length(h2))，而且只用了一個額外的指針來存儲最後一個節點。這個方法時間複雜度為線性O(N)，空間複雜度為O(1)，顯然比解法三更勝一籌。

解法四的代碼如下：

//判斷兩個鏈表是否相交
bool isIntersect(Node *h1,Node *h2)
{
    if(h1 == NULL || h2 == NULL) return false;    //異常判斷
    while(h1->next != NULL)
    {
        h1 = h1->next;
    }

    while(h2->next != NULL)
    {
        h2 = h2->next;
    }

    if(h1 == h2) return true;        //尾節點是否相同
    else return false;
}

##8. 擴展：鏈表有環，如何判斷相交 ###題目描述：上面的問題都是針對鏈表無環的，那麼如果現在，鏈表是有環的呢?上面的方法還同樣有效麼?

###分析：如果有環且兩個鏈表相交，則兩個鏈表都有共同一個環，即環上的任意一個節點都存在於兩個鏈表上。因此，就可以判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。

代碼如下：

//判斷兩個帶環鏈表是否相交
bool isIntersectWithLoop(Node *h1,Node *h2)
{
    Node *circleNode1,*circleNode2;
    if(!hasCircle(h1,circleNode1))    //判斷鏈錶帶不帶環，並保存環內節點
        return false;                //不帶環，異常退出
    if(!hasCircle(h2,circleNode2))
        return false;

    Node *temp = circleNode2->next;
    while(temp != circleNode2)
    {
        if(temp == circleNode1)
            return true;
        temp = temp->next;
    }
    return false;
}

##9. 擴展：兩鏈表相交的第一個公共節點 ###題目描述：如果兩個無環單鏈表相交，怎麼求出他們相交的第一個節點呢？

###分析：採用對齊的思想。計算兩個鏈表的長度 L1 , L2，分別用兩個指針 p1 , p2 指向兩個鏈表的頭，然後將較長鏈表的 p1（假設為 p1）向後移動L2 - L1個節點，然後再同時向後移動p1 , p2，直到 p1 = p2。相遇的點就是相交的第一個節點。

代碼如下：

//求兩鏈表相交的第一個公共節點
Node* findIntersectNode(Node *h1,Node *h2)
{
    int len1 = listLength(h1);          //求鏈表長度
    int len2 = listLength(h2);
    //對齊兩個鏈表
    if(len1 > len2)
    {
        for(int i=0;i<len1-len2;i++)
            h1=h1->next;
    }
    else 
    {
        for(int i=0;i<len2-len1;i++)
            h2=h2->next;
    }

    while(h1 != NULL)
    {
        if(h1 == h2)
            return h1;
        h1 = h1->next;
        h2 = h2->next;    
    }
    return NULL;
}

##10. 總結可以發現，在鏈表的問題中，通過兩個的指針來提高效率是很值得考慮的一個解決方案，所以一定要記住這種解題思路。記住幾種典型的鏈表問題解決方案，很多類似的題目都可以轉換到熟悉的問題再解決。

##參考文獻

程序員編程藝術：第九章、閒話鏈表追趕問題
判斷單鏈表是否存在環，判斷兩個鏈表是否相交問題詳解
面試算法之鏈表操作集錦

软件开发平台及语言笔记大全(超详细)

面試精選：鏈表問題集錦

2. 單鏈表的轉置

Shell脚本编程30分钟入门

嵌入式 Linux 知识库

笨办法学 Linux

TensorFlow 官方文档中文版

postgresql教程

笨办法学C