題目：輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。鏈表結(jié)點(diǎn)定義如下：

struct ListNode
{
????? int ??????m_nKey;
????? ListNode* m_pNext;
};

分析：為了得到倒數(shù)第k個(gè)結(jié)點(diǎn)，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步。可是輸入的是單向鏈表，只有從前往后的指針而沒有從后往前的指針。因此我們需要打開我們的思路。

既然不能從尾結(jié)點(diǎn)開始遍歷這個(gè)鏈表，我們還是把思路回到頭結(jié)點(diǎn)上來。假設(shè)整個(gè)鏈表有n個(gè)結(jié)點(diǎn)，那么倒數(shù)第k個(gè)結(jié)點(diǎn)是從頭結(jié)點(diǎn)開始的第n-k-1個(gè)結(jié)點(diǎn)（從0開始計(jì)數(shù)）。如果我們能夠得到鏈表中結(jié)點(diǎn)的個(gè)數(shù)n，那我們只要從頭結(jié)點(diǎn)開始往后走n-k-1步就可以了。如何得到結(jié)點(diǎn)數(shù)n？這個(gè)不難，只需要從頭開始遍歷鏈表，每經(jīng)過一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器加一就行了。

這種思路的時(shí)間復(fù)雜度是O(n)，但需要遍歷鏈表兩次。第一次得到鏈表中結(jié)點(diǎn)個(gè)數(shù)n，第二次得到從頭結(jié)點(diǎn)開始的第n?-k-1個(gè)結(jié)點(diǎn)即倒數(shù)第k個(gè)結(jié)點(diǎn)。

如果鏈表的結(jié)點(diǎn)數(shù)不多，這是一種很好的方法。但如果輸入的鏈表的結(jié)點(diǎn)個(gè)數(shù)很多，有可能不能一次性把整個(gè)鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個(gè)結(jié)點(diǎn)需要兩次從硬盤讀入到物理內(nèi)存。我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存是非常耗時(shí)間的操作。我們能不能把鏈表遍歷的次數(shù)減少到1？如果可以，將能有效地提高代碼執(zhí)行的時(shí)間效率。

如果我們?cè)诒闅v時(shí)維持兩個(gè)指針，第一個(gè)指針從鏈表的頭指針開始遍歷，在第k-1步之前，第二個(gè)指針保持不動(dòng)；在第k-1步開始，第二個(gè)指針也開始從鏈表的頭指針開始遍歷。由于兩個(gè)指針的距離保持在k-1，當(dāng)?shù)谝粋€(gè)（走在前面的）指針到達(dá)鏈表的尾結(jié)點(diǎn)時(shí)，第二個(gè)指針（走在后面的）指針正好是倒數(shù)第k個(gè)結(jié)點(diǎn)。

這種思路只需要遍歷鏈表一次。對(duì)于很長(zhǎng)的鏈表，只需要把每個(gè)結(jié)點(diǎn)從硬盤導(dǎo)入到內(nèi)存一次。因此這一方法的時(shí)間效率前面的方法要高。

思路一的參考代碼：

/// // Find the kth node from the tail of a list // Input: pListHead - the head of list // k - the distance to the tail // Output: the kth node from the tail of a list /// ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int k) {if(pListHead == NULL)return NULL;// count the nodes number in the listListNode *pCur = pListHead;unsigned int nNum = 0;while(pCur->m_pNext != NULL){pCur = pCur->m_pNext;nNum ++;}// if the number of nodes in the list is less than k// do nothingif(nNum < k)return NULL;// the kth node from the tail of a list // is the (n - k)th node from the headpCur = pListHead;for(unsigned int i = 0; i < nNum - k; ++ i)pCur = pCur->m_pNext;return pCur; }

思路二的參考代碼：

/// // Find the kth node from the tail of a list // Input: pListHead - the head of list // k - the distance to the tail // Output: the kth node from the tail of a list /// ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int k) {if(pListHead == NULL)return NULL;ListNode *pAhead = pListHead;ListNode *pBehind = NULL;for(unsigned int i = 0; i < k; ++ i){if(pAhead->m_pNext != NULL)pAhead = pAhead->m_pNext;else{// if the number of nodes in the list is less than k, // do nothingreturn NULL;}}pBehind = pListHead;// the distance between pAhead and pBehind is k// when pAhead arrives at the tail, p// Behind is at the kth node from the tailwhile(pAhead->m_pNext != NULL){pAhead = pAhead->m_pNext;pBehind = pBehind->m_pNext;}return pBehind; }

討論：這道題的代碼有大量的指針操作。在軟件開發(fā)中，錯(cuò)誤的指針操作是大部分問題的根源。因此每個(gè)公司都希望程序員在操作指針時(shí)有良好的習(xí)慣，比如使用指針之前判斷是不是空指針。這些都是編程的細(xì)節(jié)，但如果這些細(xì)節(jié)把握得不好，很有可能就會(huì)和心儀的公司失之交臂。

另外，這兩種思路對(duì)應(yīng)的代碼都含有循環(huán)。含有循環(huán)的代碼經(jīng)常出的問題是在循環(huán)結(jié)束條件的判斷。是該用小于還是小于等于？是該用k還是該用k-1？由于題目要求的是從0開始計(jì)數(shù)，而我們的習(xí)慣思維是從1開始計(jì)數(shù)，因此首先要想好這些邊界條件再開始編寫代碼，再者要在編寫完代碼之后再用邊界值、邊界值減1、邊界值加1都運(yùn)行一次（在紙上寫代碼就只能在心里運(yùn)行了）。

擴(kuò)展：和這道題類似的題目還有：輸入一個(gè)單向鏈表。如果該鏈表的結(jié)點(diǎn)數(shù)為奇數(shù)，輸出中間的結(jié)點(diǎn)；如果鏈表結(jié)點(diǎn)數(shù)為偶數(shù)，輸出中間兩個(gè)結(jié)點(diǎn)前面的一個(gè)。如果各位感興趣，請(qǐng)自己分析并編寫代碼。

?

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動(dòng)，書中的分析講解更加詳細(xì)，討論了如何才能寫出魯棒的代碼。歡迎關(guān)注。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(09)－链表中倒数第k个结点[数据结构]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。