C++單連結清單面試題

下面是C++中一些常見的單連結清單面試題，文中皆是無頭單連結清單。

如下：

我們必須建構節點，為了友善測試，我隻寫了尾插函數。

#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;

typedef struct Node
{
  Node(const int& data)
  : _data(data)
  , _pNext(NULL)
  {}
  int _data;
  Node *_pNext;
}*pNode;

void InitListNode(pNode *pHead)
{
  assert(pHead);
  *pHead = NULL;
}
void PushBack(pNode *pHead,int data)
{
  pNode NewNode = new Node(data);
  if (NULL == *pHead)
    *pHead = NewNode;
  else
  {
    pNode pCur = *pHead;
    while (pCur->_pNext)
    {
      pCur = pCur->_pNext;
    }
    pCur->_pNext = NewNode;
  }
}

1、逆序列印單連結清單

解決這個問題，我們可以利用棧的特性，先進後出。

void PrintListFromTail(pNode pHead)
{
  stack<pNode> s;                   //構造棧
  pNode pCur = pHead;

  while (pCur) 
  {
    s.push(pCur);
    pCur = pCur->_pNext;
  }

  while (!s.empty())
  {
    cout << s.top()->_data << " ";
    s.pop();
  }
  cout << endl;
}

下面我們用遞歸實作，

void PrintListFromTail(pNode pHead)
{
  if (pHead)
  {
    PrintListFromTail(pHead->_pNext);
    cout << pHead->_data << " ";
  }
  cout << endl;
}

2、删除一個無頭單連結清單的非尾結點（不能周遊連結清單）

我們可以将下一個結點的資料複制到給定的結點中，再删除下一個節點。也是以，題目中說明是非尾的結點。

void DelNotTail(pNode pos)
{
  assert(pos->_pNext);
  pNode node = pos->_pNext;
  pos->_data = node->_data;
  pos->_pNext = node->_pNext;
  delete node;
  node = NULL;
}

3、在無頭單連結清單的一個非頭節點前插入一個結點

受上題啟發，我們可以插到此節點後面，再交換兩個節點的内容

void InsertNode(pNode pos, int data)
{
  pNode pNewNode = new Node(pos->_data);
  pNewNode->_pNext = pos->_pNext;
  pos->_pNext = pNewNode;
  pos->_data = data;
}

4、單連結清單實作約瑟夫環(JosephCircle)

解釋一下約瑟夫環，它是一個數學的應用問題：已知n個人（以編号1，2，3...n分别表示）圍坐在一張圓桌周圍。

從編号為1的人開始報數，數到k的那個人出列；他的下一個人又從1開始報數，數到k的那個人又出列；依此規律重複下去，直到圓桌周圍的人隻剩下一個人。

我們要先把連結清單構成環，再确定删除點。

pNode JosephCircle(pNode& pHead,int M)
{
  pNode pCur = pHead;                 //構環
  while (pCur->_pNext != NULL)
  {
    pCur = pCur->_pNext;
  }
  pCur->_pNext = pHead;
  pNode pcur = pHead;
  while (pcur->_pNext == pcur)
  {
    while (--M)
    {
      pcur = pcur->_pNext;
    }
    //删除節點
    pNode del = pcur->_pNext;
    pcur->_pNext = del->_pNext;
    pcur->_data = del->_data;
    delete del;
    del  = NULL;
  }
  pcur->_pNext = NULL;
  pcur = pHead;
  return pcur;
}

5、逆置/反轉單連結清單

将整個連結清單逆置

void Reverse(pNode& pHead)
{
  if (pHead == NULL || pHead->_pNext == NULL)
    return;
  pNode pNewHead = NULL;
  pNode pNextCur= NULL;
  pNode pCur = pHead;
  while (pCur)
  {
    pNextCur = pCur->_pNext;
    pCur->_pNext = pNewHead;
    pNewHead = pCur;
    pCur = pNextCur;
  }
  pHead = pNewHead;
}

6、單連結清單排序

可以用冒泡排序

void BubbleSort(pNode pHead)
{
  if (pHead || pHead->_pNext)
    return;
  pNode pCur = pHead;
  pNode Tail = NULL;
  pNode pNextNode = NULL;
  while (pCur->_pNext != Tail)
  {
    while (pCur->_pNext != Tail)
    {
      pNextNode = pCur->_pNext;
      if (pCur->_data > pNextNode->_data)
        swap(pCur->_data, pNextNode->_data);
      pCur = pCur->_pNext;
    }
    Tail = pCur;
    pCur = pHead;
  }
}

7、合并兩個有序連結清單,合并後依然有序

我們要确定頭結點，必須知道兩個連結清單首元素的大小；第二步将連結清單合并；第三步确定哪一個連結清單首先周遊結束。

pNode Merge(pNode& pHead1, pNode& pHead2)
{
  if (pHead1 == NULL || pHead2 == NULL)       //如果有一個連結清單為空
    return (NULL == pHead1) ? pHead2 : pHead1;
  pNode pNewHead = NULL;
  pNode pCur1 = pHead1;
  pNode pCur2 = pHead2;
  pNode pTail = NULL;
  if (pCur1->_data > pCur2->_data)
  {
    pNewHead = pCur2;
    pTail = pNewHead;
    pCur2 = pCur2->_pNext;
  }
  else
  {
    pNewHead = pCur1;
    pTail = pNewHead;
    pCur1 = pCur1->_pNext;
  }
  while (pCur1&&pCur2)
  {
    if (pCur1->_data > pCur2->_data)
    {
      pTail->_pNext = pCur2;
      pCur2 = pCur2->_pNext;
      pTail = pTail->_pNext;
    }
    else
    {
      pTail->_pNext = pCur1;
      pCur1 = pCur1->_pNext;
      pTail = pTail->_pNext;
    }
  }
  if (NULL == pCur1)
    pTail->_pNext = pCur2;
  if (NULL == pCur2)
    pTail->_pNext = pCur1;
  return pNewHead;
}

也可以用遞歸解決

pNode Merge(pNode& pHead1, pNode& pHead2)
{
  if (pHead1 == NULL || pHead2 == NULL)       //如果有一個連結清單為空
    return (NULL == pHead1) ? pHead2 : pHead1;
  pNode pNewHead = NULL;
  pNode pCur1 = pHead1;
  pNode pCur2 = pHead2;
  if (pCur1->_data > pCur2->_data)
  {
    pNewHead = pCur2;
    pNewHead->_pNext = Merge(pCur1, pCur2->_pNext);
  }
  else
  {
    pNewHead = pCur1;
    pNewHead->_pNext = Merge(pCur1->_pNext, pCur2);
  }
  return pNewHead;
}

8. 查找單連結清單的中間節點，要求隻能周遊一次連結清單

可以考慮定義兩個指針，一個快指針一次走兩步，一個慢指針一次走一步，當快指針走到尾部，慢指針則剛好走到連結清單中間

如果連結清單是奇數個結點，剛好傳回中間的結點；如果連結清單是偶數個結點，傳回的是中間靠右的結點；
如果要傳回偶數結點的左邊的那個，則需要加個判斷連結清單結點個數是偶數還是奇數的條件，如下注釋部分。

pNode MiddleNode(pNode pHead)
{
  if (pHead == NULL)
    return NULL;
  pNode pFast = pHead;
  pNode pSlow = pHead;
  //pNode pMid = NULL;
  while ((pFast) && (pFast->_pNext ))
  {
    pFast = pFast->_pNext->_pNext;
    //pMid = pSlow;
    pSlow = pSlow->_pNext;
  }
  return pSlow;
  //return pMid;
}

9. 查找單連結清單的倒數第k個節點，要求隻能周遊一次連結清單

讓快指針先走k步，再一起走，兩個指針自然相差k步，當快指針走到尾，慢指針就是倒數k個。

pNode TailkNode(pNode pHead,size_t k)
{
  if (pHead == NULL || k == 0)
    return NULL;
  pNode pFast = pHead;
  pNode pSlow = pHead;
  while (--k)
  {
    if (pFast == NULL)
      return NULL;
    pFast = pFast->_pNext;
  }
  while (pFast->_pNext)
  {
    pFast = pFast->_pNext;
    pSlow = pSlow->_pNext;
  }
  return pSlow;
}

10. 删除連結清單的倒數第K個結點

void DelTailkNode(pNode *pHead,size_t k)
{
  //找節點
  if (pHead == NULL || k == 0)
    return;
  pNode pFast = *pHead;
  pNode pSlow = *pHead;
  pNode pPre = NULL;
  while (k--)
  {
    if (pFast == NULL)
      return;
    pFast = pFast->_pNext;
  }
  while (pFast)
  {
    pFast = pFast->_pNext;
    pPre = pSlow;
    pSlow = pSlow->_pNext;
  }
  //删除節點
  if (pSlow == *pHead)
    *pHead = (*pHead)->_pNext;
  else
    pPre->_pNext = pSlow->_pNext;
  delete pSlow;
}

11. 判斷單連結清單是否帶環？若帶環，求環的長度？求環的入口點？

還是快指針與慢指針，若帶環，快指針與慢指針肯定會在環上相遇，則傳回相遇點。

pNode HasCircle(pNode pHead)           //判斷是否帶環，傳回相遇點
{
  if (pHead == NULL)
    return NULL;
  pNode pFast = pHead;
  pNode pSlow = pHead;
  while (pFast&&pFast->_pNext)
  {
    pFast = pFast->_pNext->_pNext;
    pSlow = pSlow->_pNext;
    if (pFast == pSlow)
      return pSlow;
  }
  return NULL;
}

求環的長度，周遊一遍環即可。

size_t LengthCircle(pNode pHead)
{
  pNode pMeet = HasCircle(pHead);
  if (pHead == NULL&&pMeet == NULL)
    return 0;
  pNode Meet = pMeet;
  size_t count = 1;
  while (Meet->_pNext!= pMeet)
  {
    count++;
    Meet = Meet->_pNext;
  }
  return count;
}

求環的入口點。

我們要計算一下：

pNode EnterCircle(pNode pHead)
{
  pNode pMeet = HasCircle(pHead);
  if (pHead == NULL&&pMeet == NULL)
    return 0;
  pNode pCur = pHead;
  while (pMeet!=pCur)
  {
    pMeet = pMeet->_pNext;
    pCur = pCur->_pNext;
  }
  return pMeet;
}

12. 判斷兩個連結清單是否相交，若相交，求交點。（假設連結清單不帶環）

先考慮有什麼情況，兩個不帶環的連結清單相交，如下圖，隻能是這樣，且他們的最後的元素相等

判斷是否相交：

bool IsCross(pNode pHead1,pNode pHead2)
{
  if (NULL == pHead1 || NULL == pHead2)
    return false;
  pNode pCur1 = pHead1;
  pNode pCur2 = pHead2;
  while (pCur1->_pNext)
    pCur1 = pCur1->_pNext;
  while (pCur2->_pNext)
    pCur2 = pCur2->_pNext;
  if (pCur1 == pCur2)
    return true;
  return false;

求交點。我們可以周遊兩條連結清單，求出長度并求出長度差；讓長的先走長度差的部分；

pNode CrossNode(pNode pHead1, pNode pHead2)
{
  if (!IsCross(pHead1, pHead2))
    return NULL;
  pNode pCur1 = pHead1;
  pNode pCur2 = pHead2;
  size_t count1 = 0;
  size_t count2 = 0;
  //求長度差
  pNode tmp1 = pCur1;
  pNode tmp2 = pCur2;
  while (tmp1)
  {
    tmp1 = tmp1->_pNext;
    count1++;
  }
  while (tmp2)
  {
    tmp2 = tmp2->_pNext;
    count2++;
  }
  int count = count2 - count1;
  //求交點
  if (count > 0)                      //2比1長
  {
    while (count--)
    {
      pCur2 = pCur2->_pNext;
    }
  }
  else                                //1比二長
  {
    while (count++)
    {
      pCur1 = pCur1->_pNext;
    }
  }
  while (pCur1 != pCur2)
  {
    pCur1 = pCur1->_pNext;
    pCur2 = pCur2->_pNext;
  }
  return pCur1;
}

第二種方法，将一條連結清單的尾連到自己的頭構成環，求環的入口點。

pNode CrossNode(pNode pHead1, pNode pHead2)
{
  if (IsCross(pHead1, pHead2))
    return NULL;
  pNode pCur1 = pHead1;
  pNode pCur2 = pHead2;
  while (pCur1->_pNext)
  {
    pCur1 = pCur1->_pNext;
  }
  pCur1->_pNext = pCur2;
  pNode tmp = HasCircle(pHead1);
  return tmp;
}

13、判斷兩個連結清單是否相交，若相交，求交點。（假設連結清單可能帶環）

判斷是否相交，若帶環相交則共用一個環。

bool IsCrossWithCircle(pNode pHead1, pNode pHead2)
{
  if (NULL == pHead1 || NULL == pHead2)
    return false;
  pNode pMeet1 = HasCircle(pHead1);
  pNode pMeet2 = HasCircle(pHead2);
  //兩個連結清單都不帶環
  if (pMeet1 == NULL&&pMeet2 == NULL)
  {
    pNode pCur1 = pHead1;
    pNode pCur2 = pHead2;
    while (pCur1->_pNext)
      pCur1 = pCur1->_pNext;
    while (pCur2->_pNext)
      pCur2 = pCur2->_pNext;
    if (pCur1 == pCur2)
      return true;
    return false;
  }
  //兩個連結清單都帶環
  else if (pMeet1&&pHead2)
  {
    pNode tmp = pMeet1;
    while (tmp->_pNext != pMeet1)
    {
      if (tmp == pMeet2)
        return 1;
      tmp = tmp->_pNext;
    }
    return 0;
  }
  return 0;
}

求交點，還是構環，求環的入口點；将一條連結清單的相遇點指向自己的頭，如下：

pNode CrossNodeWithCircle(pNode pHead1, pNode pHead2)
{
  pNode pMeetNode1 = HasCircle(pHead1);
  pNode pMeetNode2 = HasCircle(pHead2);
  pNode pTmp = pMeetNode1->_pNext;
  if (pMeetNode1&&pMeetNode2)
  {
    pMeetNode1->_pNext = pHead2;
    pNode pEnter = EnterCircle(pMeetNode1);
    pMeetNode1->_pNext = pTmp;
    return pEnter;
  }
  else if (pMeetNode1 == NULL&&pMeetNode2 == NULL)
  {
    pNode pEnter = CrossNode(pHead1, pHead2);
    return pEnter;
  }
  return NULL;
}

以上函數測試如下：

void test1()
{
  pNode n;
  InitListNode(&n);
  PushBack(&n, 1);
  PushBack(&n, 2);
  PushBack(&n, 3);

  pNode m;
  InitListNode(&m);
  PushBack(&m, 4);
  PushBack(&m, 5);
  PushBack(&m, 6);

  /*PrintListFromTail(n);

  DelNotTail(n);
  PrintListFromTail(n);

  InsertNode((n->_pNext), 6);
  PrintListFromTail(n);
  */
  /*BubbleSort(n);
  PrintListFromTail(n);
  */
  //cout<<JosephCircle(n, 3)->_data;

  //Reverse(n);
  //PrintListFromTail(n);

  pNode tmp = Merge(n, m);
  PrintListFromTail(tmp);

  cout << MiddleNode(n)->_data << endl;

  //cout << TailkNode(n, 1)->_data << endl;

  /*DelTailkNode(&n, 1);
  PrintListFromTail(n);*/
}
void test2()
{
  pNode n;
  InitListNode(&n);
  PushBack(&n, 1);
  PushBack(&n, 2);
  PushBack(&n, 3);
  PushBack(&n, 4); 
  PushBack(&n, 5); 
  PushBack(&n, 6);

  //構環
  pNode tmp = n;
  pNode cur = tmp->_pNext;
  while (tmp->_pNext)
  {
    tmp = tmp->_pNext;
  }
  tmp->_pNext = cur;

  /*cout << LengthCircle(n) << endl;
  cout << EnterCircle(n)->_data << endl;
  cout << HasCircle(n)->_data << endl;*/
}
void test3()
{
  pNode n;
  InitListNode(&n);
  PushBack(&n, 1);
  PushBack(&n, 2);
  PushBack(&n, 3);
  PushBack(&n, 4);

  pNode m;
  InitListNode(&m);
  PushBack(&m, 4);
  PushBack(&m, 5);
  PushBack(&m, 6);
  PushBack(&m, 7);
  pNode tmp = n;
  while (tmp->_pNext)
  {
    tmp = tmp->_pNext;
  }
  tmp->_pNext = m->_pNext;

  cout << IsCross(n, m) << endl;
  cout << CrossNode(n, m)->_data << endl;
}
void test4()
{
  pNode n;
  InitListNode(&n);
  PushBack(&n, 1);
  PushBack(&n, 2);
  PushBack(&n, 3);
  PushBack(&n, 4);
  PushBack(&n, 5);
  PushBack(&n, 6);

  //構環
  pNode tmp1 = n;
  pNode cur1 = tmp1->_pNext;
  while (tmp1->_pNext)
  {
    tmp1 = tmp1->_pNext;
  }
  tmp1->_pNext = cur1;


  pNode m;
  InitListNode(&m);
  PushBack(&m, 1);
  PushBack(&m, 4);
  PushBack(&m, 5);
  PushBack(&m, 6);
  PushBack(&m, 7);

  //構環
  pNode tmp2 = m;
  while (tmp2->_pNext)
  {
    tmp2 = tmp2->_pNext;
  }
  tmp2->_pNext = cur1;

  cout << IsCrossWithCircle(n, m) << endl;
  cout << CrossNodeWithCircle(n, m)->_data << endl;
}

在這裡簡單介紹如何測試，就不加運作結果了，讀者可以自行測試。

14. 複雜連結清單的複制

一個連結清單的每個節點，有一個指向next指針指向下一個節點，還有一個random指針指向這個連結清單中的一個随機節點或者NULL，現在要求實作複制這個連結清單，傳回複制後的新連結清單。

第一步：将原連結清單的每一個結點都複制一份，然後連接配接在一起。如圖所示：綠色為随機指針的連接配接，黑色為Next指針的指向。如下圖：

第二步：處理連結清單底下一排的新連結清單的随機指針的連接配接。如上圖，下面為新連結清單，新連結清單的随機指針指向為舊連結清單指向的next，即：

pnew->_pRomdon = pold->_pRomdon->_pNext，如下圖：

第三步：将新連結清單分離出來，如下圖：

代碼如下，構造節點：

typedef struct Node
{
  Node(const int& data)
  :_data(data)
  , _pNext(NULL)
  , _pRomdon(NULL)
  {}

  int _data;
  Node* _pNext;
  Node* _pRomdon;
}*pNode;

void InitListNode(pNode *pHead)
{
  assert(pHead);
  *pHead = NULL;
}
void PushBack(pNode *pHead, int data)
{
  pNode NewNode = new Node(data);
  if (NULL == *pHead)
    *pHead = NewNode;
  else
  {
    pNode pCur = *pHead;
    while (pCur->_pNext)
    {
      pCur = pCur->_pNext;
    }
    pCur->_pNext = NewNode;
  }
}

為了友善測試，我增加了尋找函數和列印函數，如下代碼：

pNode find(pNode *pHead,int k)
{
  if (pHead == NULL)
    return NULL;
  pNode pCur = *pHead;
  while (pCur)
  {
    if (pCur->_data == k)
      return pCur;
    pCur = pCur->_pNext;
  }
  return NULL;
}
pNode ComplexListCopy(pNode pHead)
{
  if (NULL == pHead)
    return NULL;
  pNode pOld = pHead;
  //第一步：複制節點
  while (pOld)
  {
    pNode pNewNode = new Node(pOld->_data);
    pNewNode->_pNext = pOld->_pNext;
    pOld->_pNext = pNewNode;
    pOld = pOld->_pNext->_pNext;
  }
  pOld = pHead;
  pNode pNew = pOld->_pNext;
  //第二步：連随機指針
  while (pNew->_pNext)
  {
    if (pOld->_pRomdon)
      pNew->_pRomdon = pOld->_pRomdon->_pNext;
    pOld = pNew->_pNext;
    pNew = pOld->_pNext;
  }
  pOld = pHead;
  pNew = pHead->_pNext;
  //第三步：分離
  pNode pCur  = pNew;
  while (pCur->_pNext)
  {
    pOld->_pNext = pCur->_pNext;
    pOld = pCur->_pNext;
    pCur->_pNext = pOld->_pNext;
    pCur = pCur->_pNext;
  }
  return pNew;
}
void Print(pNode pHead)
{
  pNode pCur = pHead;
  while (pCur)
  {
    cout << pCur->_data << " ";
    pCur = pCur->_pNext;
  }
  cout << endl;
}

測試函數如下：

void test()
{
  pNode n;
  InitListNode(&n);
  PushBack(&n, 1);
  PushBack(&n, 2);
  PushBack(&n, 3);
  PushBack(&n, 4);

  Print(n);

  find(&n, 1)->_pRomdon = find(&n, 3);
  find(&n, 2)->_pRomdon = find(&n, 1);
  find(&n, 3)->_pRomdon = find(&n, 3);
  find(&n, 4)->_pRomdon = NULL;

  pNode m = ComplexListCopy(n);
  Print(m);

}

運作結果：

C++單連結清單面試題

繼續閱讀

HDU 5344 MZL's xor

UVA 590 Always on the run

FZU 1978 Repair the brackets

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

UVA 519 Puzzle (II)