【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;
  6. pos->_data = data;
  7. }
  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;
    7. if (pcur1->_data > pcur2->_data)
    8. {
    9. pNewHead = pcur2;
    10. pTail = pNewHead;
    11. pcur2 = pcur2->_pNext;
    12. }
    13. else
    14. {
    15. pNewHead = pcur1;
    16. pTail = pNewHead;
    17. pcur1 = pcur1->_pNext;
    18. }
    19. while (pcur1 && pcur2)
    20. {
    21. if (pcur1->_data > pcur2->_data)
    22. {
    23. pTail->_pNext = pcur2;
    24. pcur2 = pcur2->_pNext;
    25. pTail = pTail->_pNext;
    26. }
    27. else
    28. {
    29. pTail->_pNext = pcur1;
    30. pcur1 = pcur1->_pNext;
    31. pTail = pTail->_pNext;
    32. }
    33. }
    34. if (pcur1 == NULL)
    35. pTail->_pNext = pcur2;
    36. if (pcur2 == NULL)
    37. pTail->_pNext = pcur1;
    38. 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