程序員面試題精選(01)－把二元查找樹轉變成排序的雙向鏈表
　　題目：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結點，只調整指針的指向。
　　比如將二元查找樹
??????????????????????????????????????????? 10
????????????????????????????????????????? /??? /
??????????????????????????????????????? 6?????? 14
????????????????????????????????????? /? /???? /　 /
?????????????????????????????????? 　4???? 8? 12 　? 16

轉換成雙向鏈表
4=6=8=10=12=14=16。
　　分析：本題是微軟的面試題。很多與樹相關的題目都是用遞歸的思路來解決，本題也不例外。下面我們用兩種不同的遞歸思路來分析。
　 　思路一：當我們到達某一結點準備調整以該結點為根結點的子樹時，先調整其左子樹將左子樹轉換成一個排好序的左子鏈表，再調整其右子樹轉換右子鏈表。最近 鏈接左子鏈表的最右結點（左子樹的最大結點）、當前結點和右子鏈表的最左結點（右子樹的最小結點）。從樹的根結點開始遞歸調整所有結點。
　　思路二：我們可以中序遍歷整棵樹。按照這個方式遍歷樹，比較小的結點先訪問。如果我們每訪問一個結點，假設之前訪問過的結點已經調整成一個排序雙向鏈表，我們再把調整當前結點的指針將其鏈接到鏈表的末尾。當所有結點都訪問過之后，整棵樹也就轉換成一個排序雙向鏈表了。
參考代碼：
首先我們定義二元查找樹結點的數據結構如下：
??? struct BSTreeNode // a node in the binary search tree
??? {
??????? int????????? m_nValue; // value of node
??????? BSTreeNode? *m_pLeft;? // left child of node
??????? BSTreeNode? *m_pRight; // right child of node
??? };
思路一對應的代碼：
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
//??????? asRight - whether pNode is the right child of its parent
// Output: if asRight is true, return the least node in the sub-tree
//???????? else return the greatest node in the sub-tree
///////////////////////////////////////////////////////////////////////
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
????? if(!pNode)
??????????? return NULL;
????? BSTreeNode *pLeft = NULL;
????? BSTreeNode *pRight = NULL;

????? // Convert the left sub-tree
????? if(pNode->m_pLeft)
??????????? pLeft = ConvertNode(pNode->m_pLeft, false);

????? // Connect the greatest node in the left sub-tree to the current node
????? if(pLeft)
????? {
??????????? pLeft->m_pRight = pNode;
??????????? pNode->m_pLeft = pLeft;
????? }
????? // Convert the right sub-tree
????? if(pNode->m_pRight)
??????????? pRight = ConvertNode(pNode->m_pRight, true);
????? // Connect the least node in the right sub-tree to the current node
????? if(pRight)
????? {
??????????? pNode->m_pRight = pRight;
??????????? pRight->m_pLeft = pNode;
????? }

????? BSTreeNode *pTemp = pNode;
????? // If the current node is the right child of its parent,?
????? // return the least node in the tree whose root is the current node
????? if(asRight)
????? {
??????????? while(pTemp->m_pLeft)
????????????????? pTemp = pTemp->m_pLeft;
????? }
????? // If the current node is the left child of its parent,?
????? // return the greatest node in the tree whose root is the current node
????? else
????? {
??????????? while(pTemp->m_pRight)
????????????????? pTemp = pTemp->m_pRight;
????? }

????? return pTemp;
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
????? // As we want to return the head of the sorted double-linked list,
????? // we set the second parameter to be true
????? return ConvertNode(pHeadOfTree, true);
}
思路二對應的代碼：
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode -?????????? the head of the sub tree
//??????? pLastNodeInList - the tail of the double-linked list
///////////////////////////////////////////////////////////////////////
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
????? if(pNode == NULL)
??????????? return;

????? BSTreeNode *pCurrent = pNode;

????? // Convert the left sub-tree
????? if (pCurrent->m_pLeft != NULL)
??????????? ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

????? // Put the current node into the double-linked list
????? pCurrent->m_pLeft = pLastNodeInList;?
????? if(pLastNodeInList != NULL)
??????????? pLastNodeInList->m_pRight = pCurrent;

????? pLastNodeInList = pCurrent;

????? // Convert the right sub-tree
????? if (pCurrent->m_pRight != NULL)
??????????? ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
????? BSTreeNode *pLastNodeInList = NULL;
????? ConvertNode(pHeadOfTree, pLastNodeInList);

????? // Get the head of the double-linked list
????? BSTreeNode *pHeadOfList = pLastNodeInList;
????? while(pHeadOfList && pHeadOfList->m_pLeft)
??????????? pHeadOfList = pHeadOfList->m_pLeft;

????? return pHeadOfList;
}

?

程序員面試題精選(02)－設計包含min函數的棧
題目：定義棧的數據結構，要求添加一個min函數，能夠得到棧的最小元素。要求函數min、push以及pop的時間復雜度都是O(1)。 分析：這是去年google的一道面試題。
我看到這道題目時，第一反應就是每次push一個新元素時，將棧里所有逆序元素排序。這樣棧頂元素將是最小元素。但由于不能保證最后push進棧的元素最先出棧，這種思路設計的數據結構已經不是一個棧了。
在棧里添加一個成員變量存放最小元素（或最小元素的位置）。每次push一個新元素進棧的時候，如果該元素比當前的最小元素還要小，則更新最小元素。
乍一看這樣思路挺好的。但仔細一想，該思路存在一個重要的問題：如果當前最小元素被pop出去，如何才能得到下一個最小元素？
因 此僅僅只添加一個成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個輔助棧。每次push一個新元素的時候，同時將最小元素（或最小元素的 位置?？紤]到棧元素的類型可能是復雜的數據結構，用最小元素的位置將能減少空間消耗）push到輔助棧中；每次pop一個元素出棧的時候，同時pop輔助 棧。
參考代碼：
#include

????? void push(const T& value);
????? void pop(void);

????? const T& min(void) const;

private:
???? T> m_data;?????????????? // the elements of stack
???? size_t> m_minIndex;????? // the indices of minimum elements
};

// get the last element of mutable stack
template

// get the last element of non-mutable stack
template

// insert an elment at the end of stack
template

????? // set the index of minimum elment in m_data at the end of m_minIndex
????? if(m_minIndex.size() == 0)
??????????? m_minIndex.push_back(0);
????? else
????? {
??????????? if(value < m_data[m_minIndex.back()])
????????????????? m_minIndex.push_back(m_data.size() - 1);
??????????? else
????????????????? m_minIndex.push_back(m_minIndex.back());
????? }
}

// erease the element at the end of stack
template

// get the minimum element of stack
template

?

?

程序員面試題精選(03)－求子數組的最大和
題目：輸入一個整形數組，數組里有正數也有負數。數組中連續(xù)的一個或多個整數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求時間復雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，因此輸出為該子數組的和18。
分析：本題最初為2005年浙江大學計算機系的考研題的最后一道程序設計題，在2006年里包括google在內的很多知名公司都把本題當作面試題。由于本題在網絡中廣為流傳，本題也順利成為2006年程序員面試題中經典中的經典。
如果不考慮時間復雜度，我們可以枚舉出所有子數組并求出他們的和。不過非常遺憾的是，由于長度為n的數組有O(n2)個子數組；而且求一個長度為n的數組的和的時間復雜度為O(n)。因此這種思路的時間是O(n3)。
很容易理解，當我們加上一個正數時，和會增加；當我們加上一個負數時，和會減少。如果當前得到的和是個負數，那么這個和在接下來的累加中應該拋棄并重新清零，不然的話這個負數將會減少接下來的和。基于這樣的思路，我們可以寫出如下代碼。
參考代碼：
/////////////////////////////////////////////////////////////////////////////
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool FindGreatestSumOfSubArray
(
????? int *pData,?????????? // an array
????? unsigned int nLength, // the length of array
????? int &nGreatestSum???? // the greatest sum of all sub-arrays
)
{
????? // if the input is invalid, return false
????? if((pData == NULL) || (nLength == 0))
??????????? return false;
????? int nCurSum = nGreatestSum = 0;
????? for(unsigned int i = 0; i < nLength; i)
????? {
??????????? nCurSum = pData;
??????????? // if the current sum is negative, discard it
??????????? if(nCurSum < 0)
????????????????? nCurSum = 0;

??????????? // if a greater sum is found, update the greatest sum
??????????? if(nCurSum > nGreatestSum)
????????????????? nGreatestSum = nCurSum;
????? }
????? // if all data are negative, find the greatest element in the array
????? if(nGreatestSum == 0)
????? {
??????????? nGreatestSum = pData[0];
??????????? for(unsigned int i = 1; i < nLength; i)
??????????? {
????????????????? if(pData > nGreatestSum)
??????????????????????? nGreatestSum = pData;
??????????? }
????? }

????? return true;
}

討論：上述代碼中有兩點值得和大家討論一下：
??????????函數的返回值不是子數組和的最大值，而是一個判斷輸入是否有效的標志。如 果函數返回值的是子數組和的最大值，那么當輸入一個空指針是應該返回什么呢？返回0？那這個函數的用戶怎么區(qū)分輸入無效和子數組和的最大值剛好是0這兩中 情況呢？基于這個考慮，本人認為把子數組和的最大值以引用的方式放到參數列表中，同時讓函數返回一個函數是否正常執(zhí)行的標志。
??????????輸入有一類特殊情況需要特殊處理。當輸入數組中所有整數都是負數時，子數組和的最大值就是數組中的最大元素。

?

程序員面試題精選(04)－在二元樹中找出和為某一值的所有路徑
題目：輸入一個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。打印出和與輸入整數相等的所有路徑。
例如輸入整數22和如下二元樹
??????????????????????????????????????????? 10
?????????????????????????????????????????? /?? /
????????????????????????????????????????? 5???? 12
??????????????????????????????????????? /?? /???
???????????????????????????????????? 　4???? 7??
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹結點的數據結構定義為：
struct BinaryTreeNode // a node in the binary tree
{
????? int????????????? m_nValue; // value of node
????? BinaryTreeNode? *m_pLeft;? // left child of node
????? BinaryTreeNode? *m_pRight; // right child of node
};
分析：這是百度的一道筆試題，考查對樹這種基本數據結構以及遞歸函數的理解。
當 訪問到某一結點時，把該結點添加到路徑上，并累加當前結點的值。如果當前結點為葉結點并且當前路徑的和剛好等于輸入的整數，則當前的路徑符合要求，我們把 它打印出來。如果當前結點不是葉結點，則繼續(xù)訪問它的子結點。當前結點訪問結束后，遞歸函數將自動回到父結點。因此我們在函數退出之前要在路徑上刪除當前 結點并減去當前結點的值，以確保返回父結點時路徑剛好是根結點到父結點的路徑。我們不難看出保存路徑的數據結構實際上是一個棧結構，因為路徑要與遞歸調用 狀態(tài)一致，而遞歸調用本質就是一個壓棧和出棧的過程。
參考代碼：
///////////////////////////////////////////////////////////////////////
// Find paths whose sum equal to expected sum
///////////////////////////////////////////////////////////////////////
void FindPath
(
????? BinaryTreeNode*?? pTreeNode,??? // a node of binary tree
????? int?????????????? expectedSum,? // the expected sum
????? std::vector

????? // if the node is not a leaf, goto its children
????? if(pTreeNode->m_pLeft)
??????????? FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
????? if(pTreeNode->m_pRight)
??????????? FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);

????? // when we finish visiting a node and return to its parent node,
????? // we should delete this node from the path and?
????? // minus the node's value from the current sum
????? currentSum -= pTreeNode->m_nValue;
????? path.pop_back();
}

?

程序員面試題精選(05)－查找最小的k個元素
題目：輸入n個整數，輸出其中最小的k個。
例如輸入1，2，3，4，5，6，7和8這8個數字，則最小的4個數字為1，2，3和4。
分析：這道題最簡單的思路莫過于把輸入的n個整數排序，這樣排在最前面的k個數就是最小的k個數。只是這種思路的時間復雜度為O(nlogn)。我們試著尋找更快的解決思路。
我 們可以開辟一個長度為k的數組。每次從輸入的n個整數中讀入一個數。如果數組中已經插入的元素少于k個，則將讀入的整數直接放到數組中。否則長度為k的數 組已經滿了，不能再往數組里插入元素，只能替換了。如果讀入的這個整數比數組中已有k個整數的最大值要小，則用讀入的這個整數替換這個最大值；如果讀入的 整數比數組中已有k個整數的最大值還要大，則讀入的這個整數不可能是最小的k個整數之一，拋棄這個整數。這種思路相當于只要排序k個整數，因此時間復雜可 以降到O(n nlogk)。通常情況下k要遠小于n，所以這種辦法要優(yōu)于前面的思路。
這是我能夠想出來的最快的解決方案。不過從給面試官留下更 好印象的角度出發(fā)，我們可以進一步把代碼寫得更漂亮一些。從上面的分析，當長度為k的數組已經滿了之后，如果需要替換，每次替換的都是數組中的最大值。在 常用的數據結構中，能夠在O(1)時間里得到最大值的數據結構為最大堆。因此我們可以用堆（heap）來代替數組。
另外，自己重頭開始寫一個最大堆需要一定量的代碼。我們現在不需要重新去發(fā)明車輪，因為前人早就發(fā)明出來了。同樣，STL中的set和multiset為我們做了很好的堆的實現，我們可以拿過來用。既偷了懶，又給面試官留下熟悉STL的好印象，何樂而不為之？
參考代碼：
#include

????? if(k == 0 || data.size() < k)
??????????? return;
????? vector

??????????? // leastNumbers contains k numbers and it's full now
??????????? else
??????????? {
????????????????? // first number in leastNumbers is the greatest one
????????????????? IntHeap::iterator iterFirst = leastNumbers.begin();
????????????????? // if is less than the previous greatest number?
????????????????? if(*iter < *(leastNumbers.begin()))
????????????????? {
??????????????????????? // replace the previous greatest number
??????????????????????? leastNumbers.erase(iterFirst);
??????????????????????? leastNumbers.insert(*iter);
????????????????? }
??????????? }
????? }
}

?

程序員面試題精選(06)－判斷整數序列是不是二元查找樹的后序遍歷結果?
題目：輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果。如果是返回true，否則返回false。 例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的后序遍歷結果：
???????? 8
?????? /? /
????? 6??? 10
??? / /??? / /
?? 5?? 7?? 9? 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回false。
分析：這是一道trilogy的筆試題，主要考查對二元查找樹的理解。
在 后續(xù)遍歷得到的序列中，最后一個元素為樹的根結點。從頭開始掃描這個序列，比根結點小的元素都應該位于序列的左半部分；從第一個大于跟結點開始到跟結點前 面的一個元素為止，所有元素都應該大于跟結點，因為這部分元素對應的是樹的右子樹。根據這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認序列的左、右 兩部分是不是都是二元查找樹。
參考代碼：
using namespace std;
///////////////////////////////////////////////////////////////////////
// Verify whether a squence of integers are the post order traversal
// of a binary search tree (BST)
// Input: squence - the squence of integers
//??????? length? - the length of squence
// Return: return ture if the squence is traversal result of a BST,
//???????? otherwise, return false
///////////////////////////////////////////////////////////////////////
bool verifySquenceOfBST(int squence[], int length)
{
????? if(squence == NULL || length <= 0)
??????????? return false;
????? // root of a BST is at the end of post order traversal squence
????? int root = squence[length - 1];
????? // the nodes in left sub-tree are less than the root
????? int i = 0;
????? for(; i < length - 1; i)
????? {
??????????? if(squence > root)
????????????????? break;
????? }

????? // the nodes in the right sub-tree are greater than the root
????? int j = i;
????? for(; j < length - 1; j)
????? {
??????????? if(squence[j] < root)
????????????????? return false;
????? }

????? // verify whether the left sub-tree is a BST
????? bool left = true;
????? if(i > 0)
??????????? left = verifySquenceOfBST(squence, i);

????? // verify whether the right sub-tree is a BST
????? bool right = true;
????? if(i < length - 1)
??????????? right = verifySquenceOfBST(squence i, length - i - 1);

????? return (left && right);
}

?

程序員面試題精選(07)－翻轉句子中單詞的順序
題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
分析：由于編寫字符串相關代碼能夠反映程序員的編程能力和編程習慣，與字符串相關的問題一直是程序員筆試、面試題的熱門題目。本題也曾多次受到包括微軟在內的大量公司的青睞。
由于本題需要翻轉句子，我們先顛倒句子中的所有字符。這時，不但翻轉了句子中單詞的順序，而且單詞內字符也被翻轉了。我們再顛倒每個單詞內的字符。由于單詞內的字符被翻轉兩次，因此順序仍然和輸入時的順序保持一致。
還是以上面的輸入為例子。翻轉“I am a student.”中所有字符得到“.tneduts a ma I”，再翻轉每個單詞中字符的順序得到“students. a am I”，正是符合要求的輸出。
參考代碼：
///////////////////////////////////////////////////////////////////////
// Reverse a string between two pointers
// Input: pBegin - the begin pointer in a string
//??????? pEnd?? - the end pointer in a string
///////////////////////////////////////////////////////////////////////
void Reverse(char *pBegin, char *pEnd)
{
????? if(pBegin == NULL || pEnd == NULL)
??????????? return;
????? while(pBegin < pEnd)
????? {
??????????? char temp = *pBegin;
??????????? *pBegin = *pEnd;
??????????? *pEnd = temp;
??????????? pBegin , pEnd --;
????? }
}
///////////////////////////////////////////////////////////////////////
// Reverse the word order in a sentence, but maintain the character
// order inside a word
// Input: pData - the sentence to be reversed
///////////////////////////////////////////////////////////////////////
char* ReverseSentence(char *pData)
{
????? if(pData == NULL)
??????????? return NULL;

????? char *pBegin = pData;
????? char *pEnd = pData;
????? while(*pEnd != '/0')
??????????? pEnd ;
????? pEnd--;

????? // Reverse the whole sentence
????? Reverse(pBegin, pEnd);

????? // Reverse every word in the sentence
????? pBegin = pEnd = pData;
????? while(*pBegin != '/0')
????? {
??????????? if(*pBegin == ' ')
??????????? {
????????????????? pBegin ;
????????????????? pEnd ;
????????????????? continue;
??????????? }
??????????? // A word is between with pBegin and pEnd, reverse it
??????????? else if(*pEnd == ' ' || *pEnd == '/0')
??????????? {
????????????????? Reverse(pBegin, --pEnd);
????????????????? pBegin = pEnd;
??????????? }
??????????? else
??????????? {
????????????????? pEnd ;
??????????? }
????? }
????? return pData;
}

程序員面試題精選(08)－求1 2 ... n
題目：求1 2 … n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句（A?B:C）。
分析：這道題沒有多少實際意義，因為在軟件開發(fā)中不會有這么變態(tài)的限制。但這道題卻能有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對編程相關技術理解的深刻程度。
通 常求1 2 … n除了用公式n(n 1)/2之外，無外乎循環(huán)和遞歸兩種思路。由于已經明確限制for和while的使用，循環(huán)已經不能再用了。同樣， 遞歸函數也需要用if語句或者條件判斷語句來判斷是繼續(xù)遞歸下去還是終止遞歸，但現在題目已經不允許使用這兩種語句了。
我們仍然圍繞循環(huán)做文章。 循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達到這個效果。比如定義一個類，我們new一含有n個這種類型元素的數組，那么該 類的構造函數將確定會被調用n次。我們可以將需要執(zhí)行的代碼放到構造函數里。如下代碼正是基于這個思路：
class Temp
{
public:
????? Temp() { N; Sum = N; }
????? static void Reset() { N = 0; Sum = 0; }
????? static int GetSum() { return Sum; }
private:
????? static int N;
????? static int Sum;
};

int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
????? Temp::Reset();

????? Temp *a = new Temp[n];
????? delete []a;
????? a = 0;

????? return Temp::GetSum();
}
我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應該終止遞歸，我 們不妨定義兩個函數。一個函數充當遞歸函數的角色，另一個函數處理終止遞歸的情況，我們需要做的就是在兩個函數里二選一。從二選一我們很自然的想到布爾變 量，比如ture（1）的時候調用第一個函數，false（0）的時候調用第二個函數。那現在的問題是如和把數值變量n轉換成布爾值。如果對n連續(xù)做兩次 反運算，即!!n，那么非零的n轉換為true，0轉換為false。有了上述分析，我們再來看下面的代碼：
class A;
A* Array[2];

class A
{
public:
????? virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
????? virtual int Sum (int n) { return Array[!!n]->Sum(n-1) n; }
};
int solution2_Sum(int n)
{
????? A a;
????? B b;
????? Array[0] = &a;
????? Array[1] = &b;

????? int value = Array[1]->Sum(n);
????? return value;
}
這種方法是用虛函數來實現函數的選擇。當n不為零時，執(zhí)行函數B::Sum；當n為0時，執(zhí)行A::Sum。我們也可以直接用函數指針數組，這樣可能還更直接一些：
typedef int (*fun)(int);
int solution3_f1(int i)?
{
????? return 0;
}
int solution3_f2(int i)
{
????? fun f[2]={solution3_f1, solution3_f2};?
????? return i f[!!i](i-1);
}
另外我們還可以讓編譯器幫我們來完成類似于遞歸的運算，比如如下代碼：
template

template <> struct solution4_Sum

?

程序員面試題精選(09)－查找鏈表中倒數第k個結點
題目：輸入一個單向鏈表，輸出該鏈表中倒數第k個結點。鏈表的倒數第0個結點為鏈表的尾指針。鏈表結點定義如下： struct ListNode
{
????? int?????? m_nKey;
????? ListNode* m_pNext;
};
分析：為了得到倒數第k個結點，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步?？墒禽斎氲氖菃蜗蜴湵?，只有從前往后的指針而沒有從后往前的指針。因此我們需要打開我們的思路。
既 然不能從尾結點開始遍歷這個鏈表，我們還是把思路回到頭結點上來。假設整個鏈表有n個結點，那么倒數第k個結點是從頭結點開始的第n-k-1個結點（從0 開始計數）。如果我們能夠得到鏈表中結點的個數n，那我們只要從頭結點開始往后走n-k-1步就可以了。如何得到結點數n？這個不難，只需要從頭開始遍歷 鏈表，每經過一個結點，計數器加一就行了。
這種思路的時間復雜度是O(n)，但需要遍歷鏈表兩次。第一次得到鏈表中結點個數n，第二次得到從頭結點開始的第n?-k-1個結點即倒數第k個結點。
如 果鏈表的結點數不多，這是一種很好的方法。但如果輸入的鏈表的結點個數很多，有可能不能一次性把整個鏈表都從硬盤讀入物理內存，那么遍歷兩遍意味著一個結 點需要兩次從硬盤讀入到物理內存。我們知道把數據從硬盤讀入到內存是非常耗時間的操作。我們能不能把鏈表遍歷的次數減少到1？如果可以，將能有效地提高代 碼執(zhí)行的時間效率。
如果我們在遍歷時維持兩個指針，第一個指針從鏈表的頭指針開始遍歷，在第k-1步之前，第二個指針保持不動；在第k-1步開 始，第二個指針也開始從鏈表的頭指針開始遍歷。由于兩個指針的距離保持在k-1，當第一個（走在前面的）指針到達鏈表的尾結點時，第二個指針（走在后面 的）指針正好是倒數第k個結點。
這種思路只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個結點從硬盤導入到內存一次。因此這一方法的時間效率前面的方法要高。
思路一的參考代碼：
///////////////////////////////////////////////////////////////////////
// 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;
}
思路二的參考代碼：
///////////////////////////////////////////////////////////////////////
// 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)
????? {