【C++】单链表面试题

我就是我 2022-06-06 14:16 277阅读 0赞

链表是非常重要的内容，在面试时也是非常喜欢问的，下面是几个常见的面试题。

说明：这些题目中的链表都是指无头单链表。

代码的实现涉及到部分C++的语法。

  1. typedef struct Node
  2. {
  3.     Node(const int& data)
  4.     : _data(data)
  5.     , _pNext(NULL)
  6.     {}
  7.     int _data;
  8.     Node* _pNext;
  9. }*pNode;
  1. 从尾到头打印单链表

如果我们用一般的方法思考这个问题，恐怕不太好解决，如果你想到了递归，那么这道题就非常简单了。

  1. void PrintListFromTail(pNode pHead)
  2. {
  3.     if (pHead)
  4.     {
  5.         PrintListFromTail(pHead->_pNext);
  6.         cout << pHead->_data << " ";
  7.     }
  8. }

当然，我们也可以用循环来解决，不过这样就要用到栈了，因为栈先进后出的特性，方便我们解决题目。

  1. void PrintListFromTail(pNode pHead)//栈实现
  2. {
  3.     stack<pNode> s;
  4.     pNode pCur = pHead;
  5.     while (pCur)
  6.     {
  7.         s.push(pCur);
  8.         pCur = pCur->_pNext;
  9.     }
  10.     while (!s.empty())
  11.     {
  12.         cout << s.top()->_data << " ";
  13.         s.pop();
  14.     }
  15. }
  1. 删除一个无头单链表的非尾结点（不能遍历链表）

如果我们有头结点，那么这道题也就非常好做了，但是没有头结点，我们的思想是删除该结点的下一个结点，但是需要先将下一个结点的数据复制到给定的结点中，也因此，题目中说明是非尾的结点。

  1. void DelNotTail(pNode pos)
  2. {
  3.     assert(pos->_pNext);
  4.     pNode del = pos->_pNext;
  5.     pos->_data = del->_data;
  6.     pos->_pNext = del->_pNext;
  7.     delete del;
  8.     del = NULL;
  9. }
  1. 在无头单链表的一个非头节点前插入一个结点

这道题的思路与上一个题目类似，将结点插入到给定结点的后面，然后交换两个结点的数据。

  1. void InertFrontNode(pNode pos, int data)
  2. {
  3.     pNode pNewNode = new Node(pos->_data);
  4.     pNewNode->_pNext = pos->_pNext;
  5.     pos->_pNext = pNewNode;
  7.     pos->_data = data;
  8. }
  1. 单链表实现约瑟夫环(JosephCircle)

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到k的那个人出列；他的下一个人又从1开始报数，数到k的那个人又出列；依此规律重复下去，直到圆桌周围的人只剩下一个人。

  1. pNode Back(pNode pHead)//返回链表的尾节点
  2. {
  3.     pNode pCur = pHead;
  4.     while (pCur->_pNext)
  5.         pCur = pCur->_pNext;
  6.     return pCur;
  7. }
  8. pNode JosephCircle(pNode& pHead, int M)
  9. {
  10.     Back(pHead)->_pNext = pHead;//将链表构成环
  11.     pNode pcur = pHead;
  12.     while (pcur->_pNext == pcur)
  13.     {
  14.         while (--M)//报数
  15.             pcur = pcur->_pNext;
  16.         pNode del = pcur->_pNext;//删结点
  17.         pcur->_pNext = del->_pNext;
  18.         pcur->_data = del->_data;
  19.         delete del;
  20.         del = NULL;
  21.     }
  22.     pcur->_pNext = NULL;
  23.     pHead = pcur;//头指针有可能改变，因此函数传引用或二级指针
  24.     return pcur;
  25. }
  1. 逆置/反转单链表

注意这道题与第1个并不是一样的，此题要求逆置链表，而第1个题目只是将链表的数据域逆序打印。

  1. void Reverse(pNode& pHead)
  2. {
  3.     pNode pcur = pHead;
  4.     if (pcur == NULL || pcur->_pNext == NULL)
  5.         return;
  6.     pNode pNewHead = NULL;
  7.     pNode pcurnext = NULL;
  8.     while (pcur)
  9.     {
  10.         pcurnext = pcur->_pNext;
  11.         pcur->_pNext = pNewHead;
  12.         pNewHead = pcur;
  13.         pcur = pcurnext;
  14.     }
  15.     pHead = pNewHead;
  16. }

  1. 单链表排序（冒泡排序）

    void BubbleSort(pNode pHead)
    {

    1.  pNode pcur = pHead;
    2.  if (pcur == NULL || pcur->_pNext == NULL)
    3.      return;
    4.  pNode pTail = NULL;
    5.  pNode pcurnext = NULL;
    6.  while (pcur->_pNext != pTail)
    7.  {
    8.      while (pcur->_pNext != pTail)
    9.      {
    10.          pcurnext = pcur->_pNext;
    11.          if (pcur->_data > pcurnext->_data)
    12.              swap(pcur->_data, pcurnext->_data);
    13.          pcur = pcur->_pNext;
    14.      }
    15.      pTail = pcur;
    16.      pcur = pHead;
    17.  }

    }

  2. 合并两个有序链表,合并后依然有序

    pNode Merge(pNode& pHead1, pNode& pHead2)
    {

    1.  if (NULL == pHead1 || NULL == pHead2)
    2.      return (NULL == pHead1) ? pHead2 : pHead1;
    3.  pNode pNewHead = NULL;
    4.  pNode pTail = NULL;
    5.  pNode pcur1 = pHead1;
    6.  pNode pcur2 = pHead2;
    8.  if (pcur1->_data > pcur2->_data)
    9.  {
    10.      pNewHead = pcur2;
    11.      pTail = pNewHead;
    12.      pcur2 = pcur2->_pNext;
    13.  }
    14.  else
    15.  {
    16.      pNewHead = pcur1;
    17.      pTail = pNewHead;
    18.      pcur1 = pcur1->_pNext;
    19.  }
    20.  while (pcur1 && pcur2)
    21.  {
    22.      if (pcur1->_data > pcur2->_data)
    23.      {
    24.          pTail->_pNext = pcur2;
    25.          pcur2 = pcur2->_pNext;
    26.          pTail = pTail->_pNext;
    27.      }
    28.      else
    29.      {
    30.          pTail->_pNext = pcur1;
    31.          pcur1 = pcur1->_pNext;
    32.          pTail = pTail->_pNext;
    33.      }
    34.  }
    35.  if (pcur1 == NULL)
    36.      pTail->_pNext = pcur2;
    37.  if (pcur2 == NULL)
    38.      pTail->_pNext = pcur1;
    39.  return pNewHead;

    }

当然这道题，我们也可以用递归来写。 

  1. pNode Merge(pNode& pHead1, pNode& pHead2)
  2. {
  3.     if (NULL == pHead1 || NULL == pHead2)
  4.         return (NULL == pHead1) ? pHead2 : pHead1;
  5.     pNode pcur1 = pHead1;
  6.     pNode pcur2 = pHead2;
  7.     pNode pNewHead = NULL;
  8.     if (pcur1->_data < pcur2->_data)
  9.     {
  10.         pNewHead = pcur1;
  11.         pNewHead->_pNext = Merge(pcur1->_pNext, pcur2);
  12.     }
  13.     else
  14.     {
  15.         pNewHead = pcur2;
  16.         pNewHead->_pNext = Merge(pcur1, pcur2->_pNext);
  17.     }
  18.     return pNewHead;
  19. }
  1. 查找单链表的中间节点，要求只能遍历一次链表

这道题目，我们需要定义两个指针，一个快指针一次走两步，一个慢指针一次走一步，当快指针走到尾部，慢指针则刚好走到链表中间。

  1. pNode MidNode(pNode pHead)
  2. {
  3.     if (pHead == NULL)
  4.         return NULL;
  5.     pNode fast = pHead;
  6.     pNode slow = pHead;
  7.     pNode midleft = NULL;
  8.     while (fast && fast->_pNext)
  9.     {
  10.         fast = fast->_pNext->_pNext;
  11.         midleft = slow;
  12.         slow = slow->_pNext;
  13.     }
  14.     return slow;//如果链表是奇数个结点，刚好返回中间的结点；如果链表是偶数个结点，返回的是中间靠右的结点；
  15.                     //如果要返回偶数结点的左边，则需要加个判断链表结点个数是偶数还是奇数的条件，如果是偶数，则return midleft
  16. }
  1. 查找单链表的倒数第k个节点，要求只能遍历一次链表

这道题目与上一个思路基本相似，我们可以让一个指针先走K步，然后在一起走。

  1. pNode BackKNode(pNode pHead, size_t K)
  2. {
  3.     if (pHead == NULL || K == 0)
  4.         return NULL;
  5.     pNode front = pHead;
  6.     pNode back = pHead;
  7.     while (K--)
  8.     {
  9.         if (front == NULL)
  10.             return NULL;
  11.         front = front->_pNext;
  12.     }
  13.     while (front)
  14.     {
  15.         front = front->_pNext;
  16.         back = back->_pNext;
  17.     }
  18.     return back;
  19. }

  1. 删除链表的倒数第K个结点

    void DelKNode(pNode* pHead, size_t K)
    {

    1. //查找结点
    2. if (pHead == NULL || K == 0)
    3.     return;
    4. pNode front = *pHead;
    5. pNode back = *pHead;
    6. pNode preback = *pHead;
    7. while (K--)
    8. {
    9.     if (front == NULL)
    10.         return;
    11.     front = front->_pNext;
    12. }
    13. while (front)
    14. {
    15.     front = front->_pNext;
    16.     preback = back;
    17.     back = back->_pNext;
    18. }
    19. //删除结点
    20. if (back == *pHead)
    21.     *pHead = (*pHead)->_pNext;
    22. else
    23.     preback->_pNext = back->_pNext;
    24. delete back;

    }

  2. 判断单链表是否带环？若带环，求环的长度？求环的入口点？

我们可以定义两个指针，一个一次走一步，一个一次走两步；如果有环的话，那么两个指针就会相遇。

  1. pNode HasCircle(pNode pHead)//返回相遇点
  2. {
  3.     if (NULL == pHead)
  4.         return NULL;
  5.     pNode pFast = pHead;
  6.     pNode pSlow = pHead;
  7.     while (pFast && pFast->_pNext)
  8.     {
  9.         pFast = pFast->_pNext->_pNext;
  10.         pSlow = pSlow->_pNext;
  11.         if (pFast == pSlow)
  12.             return pSlow;
  13.     }
  14.     return NULL;
  15. }

定义一个count变量，从相遇点开始遍历环一圈。

  1. int CircleLength(pNode pHead)
  2. {
  3.     pNode meet = HasCircle(pHead);
  4.     if (pHead == NULL || meet == NULL)
  5.         return 0;
  6.     pNode pcur = meet;
  7.     int count = 1;
  8.     while (pcur->_pNext != meet)
  9.     {
  10.         pcur = pcur->_pNext;
  11.         count++;
  12.     }
  13.     return count;
  14. }

SouthEast

  1. pNode CircleEntry(pNode pHead)//环的入口点
  2. {
  3.     pNode pcur = pHead;
  4.     pNode pmeet = HasCircle(pHead);
  5.     if (NULL == pHead || pmeet == NULL)
  6.         return NULL;
  7.     while (pcur != pmeet)
  8.     {
  9.         pmeet = pmeet->_pNext;
  10.         pcur = pcur->_pNext;
  11.         if (pmeet == pcur)
  12.             return pmeet;
  13.     }
  14.     return NULL;
  15. }
  1. 判断两个链表是否相交，若相交，求交点。（假设链表不带环）

两个不带环的链表相交，只能是这样：

SouthEast 1 

  1. bool Is2ListCross(pNode pHead1, pNode pHead2)//判断是否相交
  2. {
  3.     if (NULL == pHead1 || NULL == pHead2)
  4.         return false;
  5.     pNode pcur1 = pHead1;
  6.     pNode pcur2 = pHead2;
  7.     while (pcur1->_pNext)
  8.         pcur1 = pcur1->_pNext;
  9.     while (pcur2->_pNext)
  10.         pcur2 = pcur2->_pNext;
  11.     if (pcur1 == pcur2)
  12.         return true;
  13.     return false;
  14. }

如上图所示：我们可以分别计算两个链表的结点个数，然后用大的减去小的，让较长的链表先走相减的结果步，然后在同时走，相遇的结点就是交点。

  1. int Size(pNode pHead)//求链表结点个数
  2. {
  3.     pNode pcur = pHead;
  4.     int count = 0;
  5.     while (pcur)
  6.     {
  7.         pcur = pcur->_pNext;
  8.         count++;
  9.     }
  10.     return count;
  11. }
  12. pNode CrossNode(pNode pHead1, pNode pHead2)//返回交点
  13. {
  14.     if (!Is2ListCross(pHead1, pHead2))
  15.         return NULL;
  16.     int len1 = Size(pHead1);
  17.     int len2 = Size(pHead2);
  18.     pNode pcur1 = pHead1;
  19.     pNode pcur2 = pHead2;
  20.     int gab = len1 - len2;
  21.     if (gab >= 0)
  22.     {
  23.         while (gab--)
  24.             pcur1 = pcur1->_pNext;
  25.     }
  26.     else
  27.     {
  28.         while (gab++)
  29.             pcur2 = pcur2->_pNext;
  30.     }
  31.     while (pcur1 != pcur2)
  32.     {
  33.         pcur1 = pcur1->_pNext;
  34.         pcur2 = pcur2->_pNext;
  35.     }
  36.     return pcur1;
  37. }

还有一种思路是，将链表的尾部连接到另一个链表的头。这样就构成了一个环，我们求环的入口点就是交点。

  1. pNode CrossNode(pNode pHead1, pNode pHead2)//两个相交的链表 构成环，求入口点
  2. {
  3.     if (!Is2ListCross(pHead1, pHead2))//是否相交
  4.         return NULL;
  5.     pNode pcur1 = pHead1;
  6.     while (pcur1->_pNext)
  7.         pcur1 = pcur1->_pNext;
  8.     pcur1->_pNext = pHead2;
  9.     pNode tmp = CircleEntry(pHead1);
  10.     return tmp;
  11. }
  1. 判断两个链表是否相交，若相交，求交点。（假设链表可能带环）

如果两个链表可能带环，我们可以分为以下几种情况：

SouthEast 2

两个带环的链表相交只能是这两种

  1. bool IsCrossWithCircle(pNode pHead1, pNode pHead2)//两个可能带环的链表是否相交
  2. {
  3.     pNode pMeetNode1 = HasCircle(pHead1);//返回第一个带环链表的相遇点，如果不带环，返回NULL
  4.     pNode pMeetNode2 = HasCircle(pHead2);//返回第二个带环链表的相遇点，如果不带环，返回NULL
  5.     if (pMeetNode1==NULL && pMeetNode2==NULL)//两个链表都不带环
  6.     {
  7.         pNode pcur1 = pHead1;
  8.         pNode pcur2 = pHead2;
  9.         while (pcur1->_pNext)
  10.             pcur1 = pcur1->_pNext;
  11.         while (pcur2->_pNext)
  12.             pcur2 = pcur2->_pNext;
  13.         if (pcur1 == pcur2)
  14.             return 1;
  15.     }
  16.     else if (pMeetNode1 && pMeetNode2)//两个链表都带环
  17.     {
  18.         pNode pcur = pHead1;//第一个相遇点开始遍历环一圈，如果第二个链表的相遇点也在环上，那么两个链表相交
  19.         while (pcur->_pNext)
  20.         {
  21.             if (pcur == pMeetNode2)
  22.                 return 2;
  23.             pcur = pcur->_pNext;
  24.         }
  25.         if (pcur == pMeetNode2)
  26.             return 2;
  27.     }
  28.     return false;
  29. }

从第一个链表的相遇点断开环，记录相遇点的下一个结点，将相遇点连接到第二个链表的头，相当于求链表环的入口点，最后再将链表恢复原样。

如图所示：

SouthEast 3

除此之外，我们还可以求出环的入口点，这样从链表头部到环入口点可以看成求两个不带环的链表的交点

  1. pNode CrossNodeWithCircle(pNode pHead1, pNode pHead2)//两个带环的链表相交，返回交点
  2. {
  3.     pNode pMeetNode1 = HasCircle(pHead1);
  4.     pNode pMeetNode2 = HasCircle(pHead2);
  5.     pNode tmp = pMeetNode1->_pNext;//第一个链表相遇点的下一个结点
  6.     if (pMeetNode1 && pMeetNode2)//两个链表都带环
  7.     {
  8.         pMeetNode1->_pNext = pHead2;
  9.         pNode CrossNode = CircleEntry(pHead1);
  10.         pMeetNode1->_pNext = tmp;//恢复原链表
  11.         return CrossNode;
  12.     }
  13.     return NULL;
  14. }

  1. 复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。

    typedef struct Node
    {

    1. Node(const int& data)
    2. : _data(data)
    3. , _pNext(NULL)
    4. , _pRomdon(NULL)
    5. {}
    6. int _data;
    7. Node* _pNext;
    8. Node* _pRomdon;

    }*pNode;

复杂链表的复制可以分为三个步骤：

第一步：将原链表的每一个结点都复制一份，然后连接在一起。如图所示：绿色为随机指针的连接，黑色为Next指针的指向。

SouthEast 4

第二步：处理链表底下一排的新链表的随机指针的连接。pnew->_pRomdon = pold->_pRomdon->_pNext;
SouthEast 5

第三步：将新链表分离出来
SouthEast 6

  1. pNode ComplexListCopy(pNode pHead)
  2. {
  3.     if (NULL == pHead)
  4.         return NULL;
  5.     pNode pold = pHead;
  6.     while (pold)//复制结点
  7.     {
  8.         pNode pNewNode = new Node(pold->_data);
  9.         pNewNode->_pNext = pold->_pNext;
  10.         pold->_pNext = pNewNode;
  11.         pold = pold->_pNext->_pNext;
  12.     }
  13.     pold = pHead;//指向随机指针
  14.     pNode pnew = pold->_pNext;
  15.     while (pold)
  16.     {
  17.         if (NULL != pold->_pRomdon)
  18.             pnew->_pRomdon = pold->_pRomdon->_pNext;
  19.         pold = pnew->_pNext;
  20.         if (pold != NULL)
  21.             pnew = pold->_pNext;
  22.     }
  23.     pold = pHead;
  24.     pnew = pold->_pNext;
  25.     pNode pcur = pnew;
  26.     while (pnew->_pNext)//分离
  27.     {
  28.         pold->_pNext = pnew->_pNext;
  29.         pold = pnew->_pNext;
  30.         pnew->_pNext = pold->_pNext;
  31.         pnew = pnew->_pNext;
  32.     }
  33.     return pcur;
  34. }

发表评论

表情：
评论列表 （有 0 条评论，277人围观）

还没有评论，来说两句吧...

相关阅读

    相关 【C++】单链表面试题

    链表是非常重要的内容，在面试时也是非常喜欢问的，下面是几个常见的面试题。 说明：这些题目中的链表都是指无头单链表。 代码的实现涉及到部分C++的语法。 typed

    我就是我我就是我/ 0 赞/ 278 阅读