面接でよく聞かれるチェーンテーブルのテーマ

注:本文はコンピュータ芸術のブログから転載して、作者の整理に感謝します!
http://blog.csdn.net/walkinginthewind/article/details/7393134
 
チェーンテーブルは最も基本的なデータ構造であり、面接官もよくチェーンテーブルで面接者の基本的な能力を考察し、チェーンテーブルに関する操作は相対的に簡単で、コードを書く能力を考察するのに適している.チェーンテーブルの操作もポインタから離れられず、ポインタがエラーを起こしやすい.多方面の原因を総合して、チェーンテーブルのテーマは面接の中で重要な地位を占めています.本文はチェーンテーブルに関する面接問題を全面的に整理し、仕事を探している学生に役立つことを望んでいます.
チェーンテーブルのノード宣言は次のとおりです.
struct ListNode{    int m_nKey;    ListNode * m_pNext;
};
 
タイトルリスト:
1. 単鎖の表の中で結点の個数を求めます 2.シングルチェーンテーブルを反転 3.単一チェーンテーブルの最後からK番目のノードを検索する(k>0) 4.単一チェーンテーブルの中間ノードの検索 5.末尾からシングルチェーンテーブルを印刷する 6. 2つの単一チェーンテーブルpHead 1とpHead 2がそれぞれ秩序化されていることが知られており、それらを1つのチェーンテーブルに統合しても秩序化されている。 7.単一チェーンテーブルにループがあるかどうかを判断する 8.2つのシングルチェーンテーブルが交差しているかどうかを判断する 9.2つの単一チェーンテーブルが交差する最初のノードを求める 10.単一チェーンテーブルにリングが存在することが知られており、リングに入る最初のノードを求める 11.単一リンクヘッダポインタpHeadとノードポインタpToBeDeleted,O(1)時間複雑度削除ノードpToBeDeletedを与える
 
詳細な回答
1. 単鎖の表の中で結点の個数を求めます
これは最も基本的なことで、正しいコードをすばやく書くことができ、チェーンテーブルが空であるかどうかをチェックすることに注意しなければならない.時間的複雑度はO(n)であった.参照コードは次のとおりです.
 

 1 //             

 2 unsigned int GetListLength(ListNode * pHead)  

 3 {  

 4     if(pHead == NULL)  

 5         return 0;  

 6   

 7     unsigned int nLength = 0;  

 8     ListNode * pCurrent = pHead;  

 9     while(pCurrent != NULL)  

10     {  

11         nLength++;  

12         pCurrent = pCurrent->m_pNext;  

13     }  

14     return nLength;  

15 }  

 
2.シングルチェーンテーブルを反転
最初から最後まで元のチェーンテーブルを遍歴し、1つのノードを遍歴するたびに、新しいチェーンテーブルの先端に取り外します.チェーンテーブルが空で、ノードが1つしかない場合に注意してください.時間的複雑度はO(n)であった.参照コードは次のとおりです.

 1 //        

 2 ListNode * ReverseList(ListNode * pHead)  

 3 {  

 4         //              ，    ，            

 5     if(pHead == NULL || pHead->m_pNext == NULL)    

 6         return pHead;  

 7   

 8     ListNode * pReversedHead = NULL; //           ，   NULL  

 9     ListNode * pCurrent = pHead;  

10     while(pCurrent != NULL)  

11     {  

12         ListNode * pTemp = pCurrent;  

13         pCurrent = pCurrent->m_pNext;  

14         pTemp->m_pNext = pReversedHead; //        ，           

15         pReversedHead = pTemp;  

16     }  

17     return pReversedHead;  

18 } 

 
 
3.単一チェーンテーブルの最後からK番目のノードを検索する(k>0)
最も一般的な方法は,単一チェーンテーブルにおけるノードの個数を統計してから,(n−k)番目のノードを見つけることである.注意チェーンテーブルが空、kが0、kが1、kがチェーンテーブルのノード数より大きい場合.時間的複雑度はO(n)であった.コード略.
ここでは主に別の考え方を話しますが、このような考え方は他のテーマでも応用されています.
主な考え方は、2つのポインタを用いて、まず前のポインタをk番目の接点に向かわせることであり、このように前後の2つのポインタの距離差はk-1であり、その後前後の2つのポインタが一緒に前進し、前のポインタが最後の接点に着いたとき、後のポインタが指す接点はk番目の接点である.
参照コードは次のとおりです.

 1 //          K     

 2 ListNode * RGetKthNode(ListNode * pHead, unsigned int k) //       R      

 3 {  

 4     if(k == 0 || pHead == NULL) //   k     1   ， k 0       NULL  

 5         return NULL;  

 6   

 7     ListNode * pAhead = pHead;  

 8     ListNode * pBehind = pHead;  

 9     while(k > 1 && pAhead != NULL) //            k     

10     {  

11         pAhead = pAhead->m_pNext;  

12         k--;  

13     }  

14     if(k > 1)     //       k，  NULL  

15         return NULL;  

16     while(pAhead->m_pNext != NULL)  //            ，                 

17     {  

18         pBehind = pBehind->m_pNext;  

19         pAhead = pAhead->m_pNext;  

20     }  

21     return pBehind;  //               k     

22 }  

 
4.単一チェーンテーブルの中間ノードの検索
この問題は前の問題と似たような思想に応用できる.2つのポインタも設定されていますが、ここでは、2つのポインタが同時に前に進み、前のポインタが2歩進むたびに、後ろのポインタが1歩進むたびに、前のポインタが最後のノードに達すると、後ろのポインタが指すノードが中間ノード、すなわち(n/2+1)番目のノードになります.注意チェーンテーブルが空で、チェーンテーブルのノード数が1と2の場合.時間複雑度O(n).参照コードは次のとおりです.
 

 1 //          ，      n(n>0)，    n/2+1     

 2 ListNode * GetMiddleNode(ListNode * pHead)  

 3 {  

 4     if(pHead == NULL || pHead->m_pNext == NULL) //            ，       

 5         return pHead;  

 6   

 7     ListNode * pAhead = pHead;  

 8     ListNode * pBehind = pHead;  

 9     while(pAhead->m_pNext != NULL) //          ，          ，           

10     {  

11         pAhead = pAhead->m_pNext;  

12         pBehind = pBehind->m_pNext;  

13         if(pAhead->m_pNext != NULL)  

14             pAhead = pAhead->m_pNext;  

15     }  

16     return pBehind; //                  

17 }  

 
5.末尾からシングルチェーンテーブルを印刷する
このような順序を逆さまにする問題に対して、私たちはスタックを考えて、後進して先に出ます.だから、この問題は自分でスタックを使うか、システムにスタックを使わせるか、つまり再帰します.チェーンテーブルが空の場合に注意してください.時間的複雑度はO(n)であった.参照コードは次のとおりです.
自分でスタックを使用する:
 

 1 //         ，     

 2 void RPrintList(ListNode * pHead)  

 3 {  

 4     std::stack<ListNode *> s;  

 5     ListNode * pNode = pHead;  

 6     while(pNode != NULL)  

 7     {  

 8         s.push(pNode);  

 9         pNode = pNode->m_pNext;  

10     }  

11     while(!s.empty())  

12     {  

13         pNode = s.top();  

14         printf("%d\t", pNode->m_nKey);  

15         s.pop();  

16     }  

17 }  

 
 
再帰関数の使用:

 1 //         ，      

 2 void RPrintList(ListNode * pHead)  

 3 {  

 4     if(pHead == NULL)  

 5     {  

 6         return;  

 7     }  

 8     else  

 9     {  

10         RPrintList(pHead->m_pNext);  

11         printf("%d\t", pHead->m_nKey);  

12     }  

13 }  

 
6. 2つの単一チェーンテーブルpHead 1とpHead 2がそれぞれ秩序化されていることが知られており、それらを1つのチェーンテーブルに統合しても秩序化されている.
これは集計ソートに似ています.特に、2つのチェーンテーブルが空で、そのうちの1つが空の場合に注意してください.O(1)のスペースしか必要ありません.時間複雑度はO(max(len 1,len 2))であった.参照コードは次のとおりです.

 1 //           

 2 ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)  

 3 {  

 4     if(pHead1 == NULL)  

 5         return pHead2;  

 6     if(pHead2 == NULL)  

 7         return pHead1;  

 8     ListNode * pHeadMerged = NULL;  

 9     if(pHead1->m_nKey < pHead2->m_nKey)  

10     {  

11         pHeadMerged = pHead1;  

12         pHeadMerged->m_pNext = NULL;  

13         pHead1 = pHead1->m_pNext;  

14     }  

15     else  

16     {  

17         pHeadMerged = pHead2;  

18         pHeadMerged->m_pNext = NULL;  

19         pHead2 = pHead2->m_pNext;  

20     }  

21     ListNode * pTemp = pHeadMerged;  

22     while(pHead1 != NULL && pHead2 != NULL)  

23     {  

24         if(pHead1->m_nKey < pHead2->m_nKey)  

25         {  

26             pTemp->m_pNext = pHead1;  

27             pHead1 = pHead1->m_pNext;  

28             pTemp = pTemp->m_pNext;  

29             pTemp->m_pNext = NULL;  

30         }  

31         else  

32         {  

33             pTemp->m_pNext = pHead2;  

34             pHead2 = pHead2->m_pNext;  

35             pTemp = pTemp->m_pNext;  

36             pTemp->m_pNext = NULL;  

37         }  

38     }  

39     if(pHead1 != NULL)  

40         pTemp->m_pNext = pHead1;  

41     else if(pHead2 != NULL)  

42         pTemp->m_pNext = pHead2;  

43     return pHeadMerged;  

44 } 

 
再帰的な解法もあります.

 1 ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)  

 2 {  

 3     if(pHead1 == NULL)  

 4         return pHead2;  

 5     if(pHead2 == NULL)  

 6         return pHead1;  

 7     ListNode * pHeadMerged = NULL;  

 8     if(pHead1->m_nKey < pHead2->m_nKey)  

 9     {  

10         pHeadMerged = pHead1;  

11         pHeadMerged->m_pNext = MergeSortedList(pHead1->m_pNext, pHead2);  

12     }  

13     else  

14     {  

15         pHeadMerged = pHead2;  

16         pHeadMerged->m_pNext = MergeSortedList(pHead1, pHead2->m_pNext);  

17     }  

18     return pHeadMerged;  

19 }  

 
 
7.単一チェーンテーブルにループがあるかどうかを判断する
ここでも2つのポインタが使われています.チェーンテーブルにリングがある場合、つまりポインタで遍歴すると、永遠に行き詰まることはありません.そのため、私たちは2つのポインタで遍歴することができて、1つのポインタは1回2歩歩いて、1つのポインタは1回1歩歩いて、もしリングがあれば、2つのポインタはきっとリングの中で出会うことができます.時間的複雑度はO(n)であった.参照コードは次のとおりです.

 1 bool HasCircle(ListNode * pHead)  

 2 {  

 3     ListNode * pFast = pHead; //            

 4     ListNode * pSlow = pHead; //            

 5     while(pFast != NULL && pFast->m_pNext != NULL)  

 6     {  

 7         pFast = pFast->m_pNext->m_pNext;  

 8         pSlow = pSlow->m_pNext;  

 9         if(pSlow == pFast) //   ，     

10             return true;  

11     }  

12     return false;  

13 }  

 
 
8.2つのシングルチェーンテーブルが交差しているかどうかを判断する
2つのチェーンテーブルがノードに交差している場合、この交差ノードの後のすべてのノードは2つのチェーンテーブルで共有されます.すなわち,2つのチェーンテーブルが交差すると,最後のノードは共有されるに違いない.最初のチェーンテーブルを巡回して、最後のノードを覚えてから、2番目のチェーンテーブルを巡回して、最後のノードに着いたときに1番目のチェーンテーブルの最後のノードと比較して、同じ場合は交差します.そうしないと交差しません.時間複雑度はO(len 1+len 2)であり、最後のノードアドレスを保存するために追加のポインタが1つしか必要ないため、空間複雑度はO(1)である.参照コードは次のとおりです.

 1 bool IsIntersected(ListNode * pHead1, ListNode * pHead2)  

 2 {  

 3         if(pHead1 == NULL || pHead2 == NULL)  

 4                 return false;  

 5   

 6     ListNode * pTail1 = pHead1;  

 7     while(pTail1->m_pNext != NULL)  

 8         pTail1 = pTail1->m_pNext;  

 9   

10     ListNode * pTail2 = pHead2;  

11     while(pTail2->m_pNext != NULL)  

12         pTail2 = pTail2->m_pNext;  

13     return pTail1 == pTail2;  

14 } 

 
 
9.2つの単一チェーンテーブルが交差する第1のノードが第1のチェーンテーブルを遍歴し、長さlen 1を計算し、同時に最後のノードのアドレスを保存することを求める.2番目のチェーンテーブルを遍歴し、長さlen 2を計算し、最後のノードが1番目のチェーンテーブルの最後のノードと同じかどうかを確認し、異なる場合は交差せずに終了します.2つのチェーンテーブルはいずれも最初のノードから始まり、len 1がlen 2より大きいと仮定すると、最初のチェーンテーブルをlen 1-len 2ノードに先に遍歴し、このとき2つのチェーンテーブルの現在のノードから最初の交差ノードまでの距離が等しくなり、その後、一緒に後ろに遍歴し、2つのノードのアドレスが同じであることを知る.
時間複雑度,O(len 1+len 2).参照コードは次のとおりです.

 1 ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)  

 2 {  

 3     if(pHead1 == NULL || pHead2 == NULL)  

 4         return NULL;  

 5   

 6     int len1 = 1;  

 7     ListNode * pTail1 = pHead1;  

 8     while(pTail1->m_pNext != NULL)  

 9     {  

10         pTail1 = pTail1->m_pNext;  

11         len1++;  

12     }  

13   

14     int len2 = 1;  

15     ListNode * pTail2 = pHead2;  

16     while(pTail2->m_pNext != NULL)  

17     {  

18         pTail2 = pTail2->m_pNext;  

19         len2++;  

20     }  

21   

22     if(pTail1 != pTail2) //        NULL  

23         return NULL;  

24   

25     ListNode * pNode1 = pHead1;  

26     ListNode * pNode2 = pHead2;  

27         //             ，             

28     if(len1 > len2)  

29     {  

30         int k = len1 - len2;  

31         while(k--)  

32             pNode1 = pNode1->m_pNext;  

33     }  

34     else  

35     {  

36         int k = len2 - len1;  

37         while(k--)  

38             pNode2 = pNode2->m_pNext;  

39     }  

40     while(pNode1 != pNode2)  

41     {  

42         pNode1 = pNode1->m_pNext;  

43         pNode2 = pNode2->m_pNext;  

44     }  

45         return pNode1;  

46 } 

 
 
10.単一チェーンテーブルにリングが存在することが知られており、リングに入る最初のノードを求める
まずループが存在するか否かを判断し,存在しなければ終了する.ループの1つのノードで切断(もちろん関数の終了時に元のチェーンテーブルを破壊することはできない)すると、2つの交差する単一チェーンテーブルが形成され、ループに入る最初のノードを求めることも2つの単一チェーンテーブルが交差する最初のノードを求めることに変換される.参照コードは次のとおりです.

 1 ListNode* GetFirstNodeInCircle(ListNode * pHead)  

 2 {  

 3     if(pHead == NULL || pHead->m_pNext == NULL)  

 4         return NULL;  

 5   

 6     ListNode * pFast = pHead;  

 7     ListNode * pSlow = pHead;  

 8     while(pFast != NULL && pFast->m_pNext != NULL)  

 9     {  

10         pSlow = pSlow->m_pNext;  

11         pFast = pFast->m_pNext->m_pNext;  

12         if(pSlow == pFast)  

13             break;  

14     }  

15     if(pFast == NULL || pFast->m_pNext == NULL)  

16         return NULL;  

17   

18     //                ，               

19     ListNode * pAssumedTail = pSlow;   

20     ListNode * pHead1 = pHead;  

21     ListNode * pHead2 = pAssumedTail->m_pNext;  

22   

23     ListNode * pNode1, * pNode2;  

24     int len1 = 1;  

25     ListNode * pNode1 = pHead1;  

26     while(pNode1 != pAssumedTail)  

27     {  

28         pNode1 = pNode1->m_pNext;  

29         len1++;  

30     }  

31       

32     int len2 = 1;  

33     ListNode * pNode2 = pHead2;  

34     while(pNode2 != pAssumedTail)  

35     {  

36         pNode2 = pNode2->m_pNext;  

37         len2++;  

38     }  

39   

40     pNode1 = pHead1;  

41     pNode2 = pHead2;  

42     //             ，             

43     if(len1 > len2)  

44     {  

45         int k = len1 - len2;  

46         while(k--)  

47             pNode1 = pNode1->m_pNext;  

48     }  

49     else  

50     {  

51         int k = len2 - len1;  

52         while(k--)  

53             pNode2 = pNode2->m_pNext;  

54     }  

55     while(pNode1 != pNode2)  

56     {  

57         pNode1 = pNode1->m_pNext;  

58         pNode2 = pNode2->m_pNext;  

59     }  

60     return pNode1;  

61 } 

 
 
11.単一リンクヘッダポインタpHeadとノードポインタpToBeDeleted,O(1)時間複雑度削除ノードpToBeDeletedを与える

 
  
 
 
  
对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点，然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1)。参考代码如下：
 
  
 
   
 1 void Delete(ListNode * pHead, ListNode * pToBeDeleted)  

 2 {  

 3     if(pToBeDeleted == NULL)  

 4         return;  

 5     if(pToBeDeleted->m_pNext != NULL)  

 6     {  

 7         pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey; //                ，           

 8         ListNode * temp = pToBeDeleted->m_pNext;  

 9         pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;  

10         delete temp;  

11     }  

12     else //              

13     {  

14         if(pHead == pToBeDeleted) //               

15         {  

16             pHead = NULL;  

17             delete pToBeDeleted;  

18         }  

19         else  

20         {  

21             ListNode * pNode = pHead;  

22             while(pNode->m_pNext != pToBeDeleted) //            

23                 pNode = pNode->m_pNext;  

24             pNode->m_pNext = NULL;  

25             delete pToBeDeleted;  

26         }     

27     }  

28 }