-查找鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

　　題目：輸入一個(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í)間效率。

　　如果我們在遍歷時(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)。

　　這種思路只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個(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 list

　　ListNode *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 nothing

　　if(nNum < k)

　　return NULL;

　　// the kth node from the tail of a list

　　// is the (n - k)th node from the head

　　pCur = pListHead;

　　for(unsigned int i = 0; i < nNum - k; ++ i)

　　pCur = pCur->m_pNext;

　　return pCur;

　　}

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識點(diǎn)總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習(xí)題匯總

　　2015軟件水平考試《程序員》知識點(diǎn)總結(jié)匯總