程序員面試題精選100題(09)-鏈表中倒數第k個結點[數據結構]

時間:2019-09-22 編輯:范文亭
題目:輸入一個單向鏈表,輸出該鏈表中倒數第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?如果可以,將能有效地提高代碼執行的時間效率。
如果我們在遍歷時維持兩個指針,第一個指針從鏈表的頭指針開始遍歷,在第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)
      {
            if(pAhead->m_pNext != NULL)
                  pAhead = pAhead->m_pNext;
            else
            {
                  // if the number of nodes in the list is less than k, 
                  // do nothing
                  return 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 tail
      while(pAhead->m_pNext != NULL)
      {
            pAhead = pAhead->m_pNext;
            pBehind = pBehind->m_pNext;
      }

      return pBehind;
}
討論:這道題的代碼有大量的指針操作。在軟件開發中,錯誤的指針操作是大部分問題的根源。因此每個公司都希望程序員在操作指針時有良好的習慣,比如使用指針之前判斷是不是空指針。這些都是編程的細節,但如果這些細節把握得不好,很有可能就會和心儀的公司失之交臂。
另外,這兩種思路對應的代碼都含有循環。含有循環的代碼經常出的問題是在循環結束條件的判斷。是該用小于還是小于等于?是該用k還是該用k-1?由于題目要求的是從0開始計數,而我們的習慣思維是從1開始計數,因此首先要想好這些邊界條件再開始編寫代碼,再者要在編寫完代碼之后再用邊界值、邊界值減1、邊界值加1都運行一次(在紙上寫代碼就只能在心里運行了)。
擴展:和這道題類似的題目還有:輸入一個單向鏈表。如果該鏈表的結點數為奇數,輸出中間的結點;如果鏈表結點數為偶數,輸出中間兩個結點前面的一個。如果各位感興趣,請自己分析并編寫代碼。
本文已影響
相關文章
大亨pk10计划苹果版