鏈表算法面試問題？看我就夠了！

airen89 2019-03-05

展開全文

1 引言

單鏈表的操作算法是筆試面試中較為常見的題目。本文將著重介紹平時面試中常見的關(guān)于鏈表的應(yīng)用題目。

本文大概一萬五千字，建議閱讀時間為一個小時，請先收藏再閱讀，平時也可以拿出來多看幾遍。

2 輸出單鏈表倒數(shù)第 K 個節(jié)點

2.1 問題描述

題目：輸入一個單鏈表，輸出此鏈表中的倒數(shù)第 K 個節(jié)點。（去除頭結(jié)點，節(jié)點計數(shù)從 1 開始）。

2.2 兩次遍歷法

2.2.1 解題思想

（1）遍歷單鏈表，遍歷同時得出鏈表長度 N 。
（2）再次從頭遍歷，訪問至第 N - K 個節(jié)點為所求節(jié)點。

2.2.2 圖解過程

2.2.3 代碼實現(xiàn)

/*計算鏈表長度*/
int listLength(ListNode* pHead){
    int count = 0;
    ListNode* pCur = pHead->next;
    if(pCur == NULL){
        printf('error');
    }
    while(pCur){
        count++;
        pCur = pCur->pNext;
    }
    return count;
}
/*查找第k個節(jié)點的值*/
ListNode* searchNodeK(ListNode* pHead, int k){
    int i = 0;
    ListNode* pCur = pHead; 
    //計算鏈表長度
    int len = listLength(pHead);
    if(k > len){
        printf('error');
    }
    //循環(huán)len-k+1次
    for(i=0; i <>1; i++){
        pCur  = pCur->next;
    }
    return pCur;//返回倒數(shù)第K個節(jié)點
}

采用這種遍歷方式需要兩次遍歷鏈表，時間復(fù)雜度為O(n※2)?？梢娺@種方式最為簡單,也較好理解，但是效率低下。

2.3 遞歸法

2.3.1 解題思想

（1）定義num = k
（2）使用遞歸方式遍歷至鏈表末尾。
（3）由末尾開始返回，每返回一次 num 減 1
（4）當(dāng) num 為 0 時，即可找到目標(biāo)節(jié)點

2.3.2 圖解過程

2.3.3 代碼實現(xiàn)

int num;//定義num值
ListNode* findKthTail(ListNode* pHead, int k) {
        num = k;
        if(pHead == NULL)
            return NULL;
        //遞歸調(diào)用
        ListNode* pCur = findKthTail(pHead->next, k);
        if(pCur != NULL)
            return pCur;
        else{
            num--;// 遞歸返回一次，num值減1
            if(num == 0)
                return pHead;//返回倒數(shù)第K個節(jié)點
            return NULL;
        }
}

使用遞歸的方式實現(xiàn)仍然需要兩次遍歷鏈表，時間復(fù)雜度為O(n※2)。

2.4 雙指針法

2.4.1 解題思想

（1）定義兩個指針 p1 和 p2 分別指向鏈表頭節(jié)點。
（2）p1 前進 K 個節(jié)點，則 p1 與 p2 相距 K 個節(jié)點。
（3）p1，p2 同時前進，每次前進 1 個節(jié)點。
（4）當(dāng) p1 指向到達鏈表末尾，由于 p1 與 p2 相距 K 個節(jié)點，則 p2 指向目標(biāo)節(jié)點。

2.4.2 圖解過程

2.4.3 代碼實現(xiàn)

ListNode* findKthTail(ListNode *pHead, int K){
    if (NULL == pHead || K == 0)
        return NULL;
    //p1，p2均指向頭節(jié)點
    ListNode *p1 = pHead;
    ListNode *p2 = pHead;
    //p1先出發(fā)，前進K個節(jié)點
    for (int i = 0; i <>
        if (p1)//防止k大于鏈表節(jié)點的個數(shù)
            p1 = p1->_next;
        else
            return NULL;
    }

    while (p1)//如果p1沒有到達鏈表結(jié)尾，則p1，p2繼續(xù)遍歷
    {
        p1 = p1->_next;
        p2 = p2->_next;
    }
    return p2;//當(dāng)p1到達末尾時，p2正好指向倒數(shù)第K個節(jié)點
}

可以看出使用雙指針法只需遍歷鏈表一次，這種方法更為高效時間復(fù)雜度為O(n)，通常筆試題目中要考的也是這種方法。

3 鏈表中存在環(huán)問題

3.1 判斷鏈表是否有環(huán)

單鏈表中的環(huán)是指鏈表末尾的節(jié)點的 next 指針不為 NULL ，而是指向了鏈表中的某個節(jié)點，導(dǎo)致鏈表中出現(xiàn)了環(huán)形結(jié)構(gòu)。

鏈表中有環(huán)示意圖：

鏈表的末尾節(jié)點 8 指向了鏈表中的節(jié)點 3，導(dǎo)致鏈表中出現(xiàn)了環(huán)形結(jié)構(gòu)。
對于鏈表是否是由有環(huán)的判斷方法有哪些呢？

3.1.1 窮舉比較法

3.1.1.1 解題思想

（1）遍歷鏈表，記錄已訪問的節(jié)點。
（2）將當(dāng)前節(jié)點與之前以及訪問過的節(jié)點比較，若有相同節(jié)點則有環(huán)。
否則，不存在環(huán)。

這種窮舉比較思想簡單，但是效率過于低下，尤其是當(dāng)鏈表節(jié)點數(shù)目較多，在進行比較時花費大量時間，時間復(fù)雜度大致在 O(n^2)。這種方法自然不是出題人的理想答案。如果筆試面試中使用這種方法，估計就要跪了，忘了這種方法吧。

3.1.2 哈希緩存法

既然在窮舉遍歷時，元素比較過程花費大量時間，那么有什么辦法可以提高比較速度呢？

3.1.2.1 解題思想

（1）首先創(chuàng)建一個以節(jié)點 ID 為鍵的 HashSe t集合，用來存儲曾經(jīng)遍歷過的節(jié)點。
（2）從頭節(jié)點開始，依次遍歷單鏈表的每一個節(jié)點。
（3）每遍歷到一個新節(jié)點，就用新節(jié)點和 HashSet 集合當(dāng)中存儲的節(jié)點作比較，如果發(fā)現(xiàn) HashSet 當(dāng)中存在相同節(jié)點 ID，則說明鏈表有環(huán)，如果 HashSet 當(dāng)中不存在相同的節(jié)點 ID，就把這個新節(jié)點 ID 存入 HashSet ，之后進入下一節(jié)點，繼續(xù)重復(fù)剛才的操作。

假設(shè)從鏈表頭節(jié)點到入環(huán)點的距離是 a ，鏈表的環(huán)長是 r 。而每一次 HashSet 查找元素的時間復(fù)雜度是 O(1), 所以總體的時間復(fù)雜度是 1 * ( a + r ) = a + r，可以簡單理解為 O(n) 。而算法的空間復(fù)雜度還是 a + r - 1，可以簡單地理解成 O(n) 。

3.1.3 快慢指針法

3.1.3.1 解題思想

（1）定義兩個指針分別為 slow，fast，并且將指針均指向鏈表頭節(jié)點。
（2）規(guī)定，slow 指針每次前進 1 個節(jié)點，fast 指針每次前進兩個節(jié)點。
（3）當(dāng) slow 與 fast 相等，且二者均不為空，則鏈表存在環(huán)。

3.1.3.2 圖解過程

無環(huán)過程：

通過圖解過程可以看出，若表中不存在環(huán)形，fast 與 slow 指針只能在鏈表末尾相遇。

有環(huán)過程：

圖解過程可以看出，若鏈表中存在環(huán)，則快慢指針必然能在環(huán)中相遇。這就好比在環(huán)形跑道中進行龜兔賽跑。由于兔子速度大于烏龜速度，則必然會出現(xiàn)兔子與烏龜再次相遇情況。因此，當(dāng)出現(xiàn)快慢指針相等時，且二者不為NULL，則表明鏈表存在環(huán)。

3.1.3.3 代碼實現(xiàn)

bool isExistLoop(ListNode* pHead)  {  
    ListNode* fast;//慢指針，每次前進一個節(jié)點
    ListNode* slow;//快指針，每次前進2個節(jié)點 
    slow = fast = pHead ;  //兩個指針均指向鏈表頭節(jié)點
    //當(dāng)沒有到達鏈表結(jié)尾，則繼續(xù)前進
    while (slow != NULL && fast -> next != NULL)  {  
        slow = slow -> next ; //慢指針前進一個節(jié)點
        fast = fast -> next -> next ; //快指針前進兩個節(jié)點
        if (slow == fast)  //若兩個指針相遇，且均不為NULL則存在環(huán)
            return true ;  
    }  
    //到達末尾仍然沒有相遇，則不存在環(huán)
    return false ;  
}

3.2 定位環(huán)入口

在 3.1 節(jié)中，已經(jīng)實現(xiàn)了鏈表中是否有環(huán)的判斷方法。那么，當(dāng)鏈表中存在環(huán)，如何確定環(huán)的入口節(jié)點呢？

3.2.1 解題思想

slow 指針每次前進一個節(jié)點，故 slow 與 fast 相遇時，slow 還沒有遍歷完整個鏈表。設(shè) slow 走過節(jié)點數(shù)為 s，fast 走過節(jié)點數(shù)為 2s。設(shè)環(huán)入口點距離頭節(jié)點為 a，slow 與 fast 首次相遇點距離入口點為 b，環(huán)的長度為 r。
則有：
s = a + b;
2s = n * r + a + b; n 代表fast指針已經(jīng)在環(huán)中循環(huán)的圈數(shù)。
則推出：
s = n * r; 意味著slow指針走過的長度為環(huán)的長度整數(shù)倍。

若鏈表頭節(jié)點到環(huán)的末尾節(jié)點度為 L，slow 與 fast 的相遇節(jié)點距離環(huán)入口節(jié)點為 X。
則有：
a+X = s = n * r = (n - 1) * r + (L - a);
a = (n - 1) * r + (L - a - X);
上述等式可以看出：
從 slow 與 fast 相遇點出發(fā)一個指針 p1，請進 (L - a - X) 步，則此指針到達入口節(jié)點。同時指針 p2 從頭結(jié)點出發(fā)，前進 a 步。當(dāng) p1 與 p2 相遇時，此時 p1 與 p2 均指向入口節(jié)點。

例如圖3.1所示鏈表：
slow 走過節(jié)點 s = 6；
fast 走過節(jié)點 2s = 12；
環(huán)入口節(jié)點據(jù)流頭節(jié)點 a = 3；
相遇點距離頭節(jié)點 X = 3；
L = 8；
r = 6；
可以得出 a = (n - 1) * r + (L - a - X)結(jié)果成立。

3.2.2 圖解過程

3.2.3 代碼實現(xiàn)

//找到環(huán)中的相遇節(jié)點
ListNode* getMeetingNode(ListNode* pHead) // 假設(shè)為帶頭節(jié)點的單鏈表
{
    ListNode* fast;//慢指針，每次前進一個節(jié)點
    ListNode* slow;//快指針，每次前進2個節(jié)點 
    slow = fast = pHead ;  //兩個指針均指向鏈表頭節(jié)點
    //當(dāng)沒有到達鏈表結(jié)尾，則繼續(xù)前進
    while (slow != NULL && fast -> next != NULL){  
        slow = slow -> next ; //慢指針前進一個節(jié)點
        fast = fast -> next -> next ; //快指針前進兩個節(jié)點
        if (slow == fast)  //若兩個指針相遇，且均不為NULL則存在環(huán)
            return slow;  
    }  

    //到達末尾仍然沒有相遇，則不存在環(huán)
    return NULL ;
}
//找出環(huán)的入口節(jié)點
ListNode* getEntryNodeOfLoop(ListNode* pHead){
    ListNode* meetingNode = getMeetingNode(pHead); // 先找出環(huán)中的相遇節(jié)點
    if (meetingNode == NULL)
        return NULL;
    ListNode* p1 = meetingNode;
    ListNode* p2 = pHead;
    while (p1 != p2) // p1和p2以相同的速度向前移動，當(dāng)p2指向環(huán)的入口節(jié)點時，p1已經(jīng)圍繞著環(huán)走了n圈又回到了入口節(jié)點。
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    //返回入口節(jié)點
    return p1;
}

3.3 計算環(huán)長度

3.3.1 解題思想

在3.1中找到了 slow 與 fast 的相遇節(jié)點，令 solw 與 fast 指針從相遇節(jié)點出發(fā)，按照之前的前進規(guī)則，當(dāng) slow 與fast 再次相遇時，slow 走過的長度正好為環(huán)的長度。

3.3.2 圖解過程

3.3.3 代碼實現(xiàn)

int getLoopLength(ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    while ( fast && fast->next ){
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast )//第一次相遇
            break;
    }
    //slow與fast繼續(xù)前進
    slow = slow->next;
    fast = fast->next->next;
    int length = 1;       //環(huán)長度
    while ( fast != slow )//再次相遇
    {
        slow = slow->next;
        fast = fast->next->next;
        length ++;        //累加
    }
    //當(dāng)slow與fast再次相遇，得到環(huán)長度
    return length;
}

4 使用鏈表實現(xiàn)大數(shù)加法

4.1 問題描述

兩個用鏈表代表的整數(shù)，其中每個節(jié)點包含一個數(shù)字。數(shù)字存儲按照在原來整數(shù)中相反的順序，使得第一個數(shù)字位于鏈表的開頭。寫出一個函數(shù)將兩個整數(shù)相加，用鏈表形式返回和。

例如：
輸入：
3->1->5->null
5->9->2->null，
輸出：
8->0->8->null

4.2 代碼實現(xiàn)

ListNode* numberAddAsList(ListNode* l1, ListNode* l2) {
        ListNode *ret = l1, *pre = l1;
        int up = 0;
        while (l1 != NULL && l2 != NULL) {
            //數(shù)值相加
            l1->val = l1->val + l2->val + up;
            //計算是否有進位
            up = l1->val / 10;
            //保留計算結(jié)果的個位
            l1->val %= 10;
            //記錄當(dāng)前節(jié)點位置
            pre = l1;
            //同時向后移位
            l1 = l1->next;
            l2 = l2->next;
        }
        //若l1到達末尾，說明l1長度小于l2
        if (l1 == NULL)
            //pre->next指向l2的當(dāng)前位置
            pre->next = l2;
        //l1指針指向l2節(jié)點當(dāng)前位置
        l1 = pre->next;
        //繼續(xù)計算剩余節(jié)點
        while (l1 != NULL) {
            l1->val = l1->val + up;
            up = l1->val / 10;
            l1->val %= 10;
            pre = l1;
            l1 = l1->next;
        }

        //最高位計算有進位，則新建一個節(jié)點保留最高位
        if (up != 0) {
            ListNode *tmp = new ListNode(up);
            pre->next = tmp;
        }
        //返回計算結(jié)果鏈表
        return ret;
}

5 有序鏈表合并

5.1 問題描述

題目：將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

示例：
輸入：
1->2->4,
1->3->4
輸出：
1->1->2->3->4->4

5.2 一般方案

5.2.1 解題思想

（1）對空鏈表存在的情況進行處理，假如 pHead1 為空則返回 pHead2 ，pHead2 為空則返回 pHead1。（兩個都為空此情況在pHead1為空已經(jīng)被攔截）
（2）在兩個鏈表無空鏈表的情況下確定第一個結(jié)點，比較鏈表1和鏈表2的第一個結(jié)點的值，將值小的結(jié)點保存下來為合并后的第一個結(jié)點。并且把第一個結(jié)點為最小的鏈表向后移動一個元素。
（3）繼續(xù)在剩下的元素中選擇小的值，連接到第一個結(jié)點后面，并不斷next將值小的結(jié)點連接到第一個結(jié)點后面，直到某一個鏈表為空。
（4）當(dāng)兩個鏈表長度不一致時，也就是比較完成后其中一個鏈表為空，此時需要把另外一個鏈表剩下的元素都連接到第一個結(jié)點的后面。

5.2.2 代碼實現(xiàn)

ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
    ListNode* pTail = NULL;//指向新鏈表的最后一個結(jié)點 pTail->next去連接
    ListNode* newHead = NULL;//指向合并后鏈表第一個結(jié)點
    if (NULL == pHead1){
        return pHead2;
    }else if(NULL == pHead2){
        return pHead1;
    }else{
        //確定頭指針
        if ( pHead1->data < phead2->data){
            newHead = pHead1;
            pHead1 = pHead1->next;//指向鏈表的第二個結(jié)點
        }else{
            newHead = pHead2;
            pHead2 = pHead2->next;
        }
        pTail = newHead;//指向第一個結(jié)點
        while ( pHead1 && pHead2) {
            if ( pHead1->data <= phead2->data ){
                pTail->next = pHead1;  
                pHead1 = pHead1->next;
            }else {
                pTail->next = pHead2;
                pHead2 = pHead2->next;
            }
            pTail = pTail->next;

        }
        if(NULL == pHead1){
            pTail->next = pHead2;
        }else if(NULL == pHead2){
            pTail->next = pHead1;
        }
        return newHead;
}

5.3 遞歸方案

5.3.1 解題思想

（1）對空鏈表存在的情況進行處理，假如 pHead1 為空則返回 pHead2 ，pHead2 為空則返回 pHead1。
（2）比較兩個鏈表第一個結(jié)點的大小，確定頭結(jié)點的位置
（3）頭結(jié)點確定后，繼續(xù)在剩下的結(jié)點中選出下一個結(jié)點去鏈接到第二步選出的結(jié)點后面，然后在繼續(xù)重復(fù)（2 ）（3）步，直到有鏈表為空。

5.3.2 代碼實現(xiàn)

ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
    ListNode* newHead = NULL;
    if (NULL == pHead1){
        return pHead2;
    }else if(NULL ==pHead2){
        return pHead2;
    }else{
        if (pHead1->data < phead2->data){
            newHead = pHead1;
            newHead->next = mergeTwoOrderedLists(pHead1->next, pHead2);
        }else{
            newHead = pHead2;
            newHead->next = mergeTwoOrderedLists(pHead1, pHead2->next);
         }
        return newHead;
    }   
}

6 刪除鏈表中節(jié)點，要求時間復(fù)雜度為O(1)

6.1 問題描述

給定一個單鏈表中的表頭和一個等待被刪除的節(jié)點。請在 O(1) 時間復(fù)雜度刪除該鏈表節(jié)點。并在刪除該節(jié)點后，返回表頭。

示例：
給定 1->2->3->4，和節(jié)點 3，返回 1->2->4。

6.2 解題思想

在之前介紹的單鏈表刪除節(jié)點中，最普通的方法就是遍歷鏈表，復(fù)雜度為O(n)。
如果我們把刪除節(jié)點的下一個結(jié)點的值賦值給要刪除的結(jié)點，然后刪除這個結(jié)點，這相當(dāng)于刪除了需要刪除的那個結(jié)點。因為我們很容易獲取到刪除節(jié)點的下一個節(jié)點，所以復(fù)雜度只需要O(1)。

示例
單鏈表：1->2->3->4->NULL
若要刪除節(jié)點 3 。第一步將節(jié)點3的下一個節(jié)點的值4賦值給當(dāng)前節(jié)點。變成 1->2->4->4->NULL，然后將就 4 這個結(jié)點刪除，就達到目的了。 1->2->4->NULL

如果刪除的節(jié)點的是頭節(jié)點，把頭結(jié)點指向 NULL。
如果刪除的節(jié)點的是尾節(jié)點，那只能從頭遍歷到頭節(jié)點的上一個結(jié)點。

6.3 圖解過程

6.4 代碼實現(xiàn)

void deleteNode(ListNode **pHead, ListNode* pDelNode) {
        if(pDelNode == NULL)
            return;
        if(pDelNode->next != NULL){
            ListNode *pNext = pDelNode->next;
            //下一個節(jié)點值賦給待刪除節(jié)點
            pDelNode->val   =  pNext->val;
            //待刪除節(jié)點指針指后面第二個節(jié)點
            pDelNode->next  = pNext->next;
            //刪除待刪除節(jié)點的下一個節(jié)點
            delete pNext;
            pNext = NULL;
        }else if(*pHead == pDelNode)//刪除的節(jié)點是頭節(jié)點
         {
            delete pDelNode;
            pDelNode= NULL;
            *pHead = NULL;
        } else//刪除的是尾節(jié)點
        {
            ListNode *pNode = *pHead;
            while(pNode->next != pDelNode) {
                pNode = pNode->next;
            }
            pNode->next = NULL;
            delete pDelNode;
            pDelNode= NULL;
        }
    }

7 從尾到頭打印鏈表

7.1 問題描述

輸入一個鏈表，按鏈表值從尾到頭的順序返回一個 ArrayList 。

7.2 解法

初看題目意思就是輸出的時候鏈表尾部的元素放在前面，鏈表頭部的元素放在后面。這不就是 先進后出，后進先出 么。

什么數(shù)據(jù)結(jié)構(gòu)符合這個要求？

棧！

7.2.1 代碼實現(xiàn)

class Solution {
public:
    vectorint> printListFromTailToHead(ListNode* head) {
        vectorint> value;
        ListNode *p=NULL;
        p=head;
        stackint> stk;
        while(p!=NULL){
            stk.push(p->val);
            p=p->next;
        }
        while(!stk.empty()){
            value.push_back(stk.top());
            stk.pop();
        }
        return value;
    }
};

7.3 解法二

第二種方法也比較容易想到，通過鏈表的構(gòu)造，如果將末尾的節(jié)點存儲之后，剩余的鏈表處理方式還是不變，所以可以使用遞歸的形式進行處理。

7.3.1 代碼實現(xiàn)

class Solution {
public:
    vectorint> value;
    vectorint> printListFromTailToHead(ListNode* head) {
        ListNode *p=NULL;
        p=head;
        if(p!=NULL){
            if(p->next!=NULL){
                printListFromTailToHead(p->next);
            }
            value.push_back(p->val);
        }
        return value;
    }
};

8 反轉(zhuǎn)鏈表

8.1 題目描述

反轉(zhuǎn)一個單鏈表。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

進階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？

8.2 解題思路

設(shè)置三個節(jié)點pre、cur、next

（1）每次查看cur節(jié)點是否為NULL，如果是，則結(jié)束循環(huán)，獲得結(jié)果
（2）如果cur節(jié)點不是為NULL，則先設(shè)置臨時變量next為cur的下一個節(jié)點
（3）讓cur的下一個節(jié)點變成指向pre，而后pre移動cur，cur移動到next
（4）重復(fù)（1）（2）（3）

8.3 動畫演示

8.4 代碼實現(xiàn)

8.4.1 迭代方式

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

8.4.2 遞歸的方式處理

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 遞歸終止條件
        if(head == NULL || head->next == NULL)
            return head;

        ListNode* rhead = reverseList(head->next);
        // head->next此刻指向head后面的鏈表的尾節(jié)點
        // head->next->next = head把head節(jié)點放在了尾部
        head->next->next = head;
        head->next = NULL;
        return rhead;
    }
};