轻松搞定面试中的链表题目

转载于 http://blog.csdn.net/luckyxiaoqiang/article/details/7393134#topic2

版权所有,转载请注明出处,谢谢! http://blog.csdn.net/walkinginthewind/article/details/7393134

链表是最基本的数据结构,面试官也常常用链表来考察面试者的基本能力,而且链表相关的操作相对而言比较简单,也适合考察写代码的能力。链表的操作也离不开指针,指针又很容易导致出错。综合多方面的原因,链表题目在面试中占据着很重要的地位。本文对链表相关的面试题做了较为全面的整理,希望能对找工作的同学有所帮助。

链表结点声明如下:

 struct ListNode
 {
     int m_nKey;
     ListNode * m_pNext;
 };

详细解答

1. 求单链表中结点的个数

这是最最基本的了,应该能够迅速写出正确的代码,注意检查链表是否为空。时间复杂度为O(n)。参考代码如下:

[cpp] view plaincopy

  1. // 求单链表中结点的个数
  2. unsigned int GetListLength(ListNode * pHead)  
  3. {  
  4. if(pHead == NULL)  
  5. return 0;  
  6.     unsigned int nLength = 0;  
  7.     ListNode * pCurrent = pHead;  
  8. while(pCurrent != NULL)  
  9.     {  
  10.         nLength++;  
  11.         pCurrent = pCurrent->m_pNext;  
  12.     }  
  13. return nLength;  
  14. }  

2. 将单链表反转

从头到尾遍历原链表,每遍历一个结点,将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O(n)。参考代码如下:

[cpp] view plaincopy

  1. // 反转单链表
  2. ListNode * ReverseList(ListNode * pHead)  
  3. {  
  4. // 如果链表为空或只有一个结点,无需反转,直接返回原链表头指针
  5. if(pHead == NULL || pHead->m_pNext == NULL)    
  6. return pHead;  
  7.     ListNode * pReversedHead = NULL; // 反转后的新链表头指针,初始为NULL
  8.     ListNode * pCurrent = pHead;  
  9. while(pCurrent != NULL)  
  10.     {  
  11.         ListNode * pTemp = pCurrent;  
  12.         pCurrent = pCurrent->m_pNext;  
  13.         pTemp->m_pNext = pReversedHead; // 将当前结点摘下,插入新链表的最前端
  14.         pReversedHead = pTemp;  
  15.     }  
  16. return pReversedHead;  
  17. }  

3. 查找单链表中的倒数第K个结点(k > 0)

最普遍的方法是,先统计单链表中结点的个数,然后再找到第(n-k)个结点。注意链表为空,k为0,k为1,k大于链表中节点个数时的情况。时间复杂度为O(n)。代码略。

这里主要讲一下另一个思路,这种思路在其他题目中也会有应用。

主要思路就是使用两个指针,先让前面的指针走到正向第k个结点,这样前后两个指针的距离差是k-1,之后前后两个指针一起向前走,前面的指针走到最后一个结点时,后面指针所指结点就是倒数第k个结点。

参考代码如下:

[cpp] view plaincopy

  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.     ListNode * pAhead = pHead;  
  7.     ListNode * pBehind = pHead;  
  8. while(k > 1 && pAhead != NULL) // 前面的指针先走到正向第k个结点
  9.     {  
  10.         pAhead = pAhead->m_pNext;  
  11.         k--;  
  12.     }  
  13. if(k > 1 || pAhead == NULL)     // 结点个数小于k,返回NULL
  14. return NULL;  
  15. while(pAhead->m_pNext != NULL)  // 前后两个指针一起向前走,直到前面的指针指向最后一个结点
  16.     {  
  17.         pBehind = pBehind->m_pNext;  
  18.         pAhead = pAhead->m_pNext;  
  19.     }  
  20. return pBehind;  // 后面的指针所指结点就是倒数第k个结点
  21. }  

4. 查找单链表的中间结点

此题可应用于上一题类似的思想。也是设置两个指针,只不过这里是,两个指针同时向前走,前面的指针每次走两步,后面的指针每次走一步,前面的指针走到最后一个结点时,后面的指针所指结点就是中间结点,即第(n/2+1)个结点。注意链表为空,链表结点个数为1和2的情况。时间复杂度O(n)。参考代码如下:

[cpp] view plaincopy

  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.     ListNode * pAhead = pHead;  
  7.     ListNode * pBehind = pHead;  
  8. while(pAhead->m_pNext != NULL) // 前面指针每次走两步,直到指向最后一个结点,后面指针每次走一步
  9.     {  
  10.         pAhead = pAhead->m_pNext;  
  11.         pBehind = pBehind->m_pNext;  
  12. if(pAhead->m_pNext != NULL)  
  13.             pAhead = pAhead->m_pNext;  
  14.     }  
  15. return pBehind; // 后面的指针所指结点即为中间结点
  16. }  

5. 从尾到头打印单链表

对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系统使用栈,也就是递归。注意链表为空的情况。时间复杂度为O(n)。参考代码如下:

自己使用栈:

[cpp] view plaincopy

  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. }  

使用递归函数:

[cpp] view plaincopy

  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. 已知两个单链表pHead1 和pHead2 各自有序,把它们合并成一个链表依然有序

这个类似归并排序。尤其注意两个链表都为空,和其中一个为空时的情况。只需要O(1)的空间。时间复杂度为O(max(len1, len2))。参考代码如下:

[cpp] view plaincopy

  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. }  

也有如下递归解法:

[cpp] view plaincopy

  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. 判断一个单链表中是否有环

这里也是用到两个指针。如果一个链表中有环,也就是说用一个指针去遍历,是永远走不到头的。因此,我们可以用两个指针去遍历,一个指针一次走两步,一个指针一次走一步,如果有环,两个指针肯定会在环中相遇。时间复杂度为O(n)。参考代码如下:

[cpp] view plaincopy

  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. 判断两个单链表是否相交

如果两个链表相交于某一节点,那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说,如果两个链表相交,那么最后一个节点肯定是共有的。先遍历第一个链表,记住最后一个节点,然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则不相交。时间复杂度为O(len1+len2),因为只需要一个额外指针保存最后一个节点地址,空间复杂度为O(1)。参考代码如下:

[cpp] view plaincopy

  1. bool IsIntersected(ListNode * pHead1, ListNode * pHead2)  
  2. {  
  3. if(pHead1 == NULL || pHead2 == NULL)  
  4. return false;  
  5.     ListNode * pTail1 = pHead1;  
  6. while(pTail1->m_pNext != NULL)  
  7.         pTail1 = pTail1->m_pNext;  
  8.     ListNode * pTail2 = pHead2;  
  9. while(pTail2->m_pNext != NULL)  
  10.         pTail2 = pTail2->m_pNext;  
  11. return pTail1 == pTail2;  
  12. }  

9. 求两个单链表相交的第一个节点 对第一个链表遍历,计算长度len1,同时保存最后一个节点的地址。 对第二个链表遍历,计算长度len2,同时检查最后一个节点是否和第一个链表的最后一个节点相同,若不相同,不相交,结束。 两个链表均从头节点开始,假设len1大于len2,那么将第一个链表先遍历len1-len2个节点,此时两个链表当前节点到第一个相交节点的距离就相等了,然后一起向后遍历,知道两个节点的地址相同。

时间复杂度,O(len1+len2)。参考代码如下:

[cpp] view plaincopy

  1. ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)  
  2. {  
  3. if(pHead1 == NULL || pHead2 == NULL)  
  4. return NULL;  
  5. int len1 = 1;  
  6.     ListNode * pTail1 = pHead1;  
  7. while(pTail1->m_pNext != NULL)  
  8.     {  
  9.         pTail1 = pTail1->m_pNext;  
  10.         len1++;  
  11.     }  
  12. int len2 = 1;  
  13.     ListNode * pTail2 = pHead2;  
  14. while(pTail2->m_pNext != NULL)  
  15.     {  
  16.         pTail2 = pTail2->m_pNext;  
  17.         len2++;  
  18.     }  
  19. if(pTail1 != pTail2) // 不相交直接返回NULL
  20. return NULL;  
  21.     ListNode * pNode1 = pHead1;  
  22.     ListNode * pNode2 = pHead2;  
  23. // 先对齐两个链表的当前结点,使之到尾节点的距离相等
  24. if(len1 > len2)  
  25.     {  
  26. int k = len1 - len2;  
  27. while(k--)  
  28.             pNode1 = pNode1->m_pNext;  
  29.     }  
  30. else
  31.     {  
  32. int k = len2 - len1;  
  33. while(k--)  
  34.             pNode2 = pNode2->m_pNext;  
  35.     }  
  36. while(pNode1 != pNode2)  
  37.     {  
  38.         pNode1 = pNode1->m_pNext;  
  39.         pNode2 = pNode2->m_pNext;  
  40.     }  
  41. return pNode1;  
  42. }  

10. 已知一个单链表中存在环,求进入环中的第一个节点

首先判断是否存在环,若不存在结束。在环中的一个节点处断开(当然函数结束时不能破坏原链表),这样就形成了两个相交的单链表,求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。参考代码如下:

[cpp] view plaincopy

  1. ListNode* GetFirstNodeInCircle(ListNode * pHead)  
  2. {  
  3. if(pHead == NULL || pHead->m_pNext == NULL)  
  4. return NULL;  
  5.     ListNode * pFast = pHead;  
  6.     ListNode * pSlow = pHead;  
  7. while(pFast != NULL && pFast->m_pNext != NULL)  
  8.     {  
  9.         pSlow = pSlow->m_pNext;  
  10.         pFast = pFast->m_pNext->m_pNext;  
  11. if(pSlow == pFast)  
  12. break;  
  13.     }  
  14. if(pFast == NULL || pFast->m_pNext == NULL)  
  15. return NULL;  
  16. // 将环中的此节点作为假设的尾节点,将它变成两个单链表相交问题
  17.     ListNode * pAssumedTail = pSlow;   
  18.     ListNode * pHead1 = pHead;  
  19.     ListNode * pHead2 = pAssumedTail->m_pNext;  
  20.     ListNode * pNode1, * pNode2;  
  21. int len1 = 1;  
  22.     ListNode * pNode1 = pHead1;  
  23. while(pNode1 != pAssumedTail)  
  24.     {  
  25.         pNode1 = pNode1->m_pNext;  
  26.         len1++;  
  27.     }  
  28. int len2 = 1;  
  29.     ListNode * pNode2 = pHead2;  
  30. while(pNode2 != pAssumedTail)  
  31.     {  
  32.         pNode2 = pNode2->m_pNext;  
  33.         len2++;  
  34.     }  
  35.     pNode1 = pHead1;  
  36.     pNode2 = pHead2;  
  37. // 先对齐两个链表的当前结点,使之到尾节点的距离相等
  38. if(len1 > len2)  
  39.     {  
  40. int k = len1 - len2;  
  41. while(k--)  
  42.             pNode1 = pNode1->m_pNext;  
  43.     }  
  44. else
  45.     {  
  46. int k = len2 - len1;  
  47. while(k--)  
  48.             pNode2 = pNode2->m_pNext;  
  49.     }  
  50. while(pNode1 != pNode2)  
  51.     {  
  52.         pNode1 = pNode1->m_pNext;  
  53.         pNode2 = pNode2->m_pNext;  
  54.     }  
  55. return pNode1;  
  56. }  

11. 给出一单链表头指针pHead和一节点指针pToBeDeleted,O(1)时间复杂度删除节点pToBeDeleted

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

[cpp] view plaincopy

  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. }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏儿童编程

《动物魔法学校》儿童学编程Scratch之“外观”部分

导读:本文通过一个案例《动物魔法学校》来学习Scratch语言的“外观”部分。之后通过一系列其他功能的综合运用对作品功能进行了扩展。

18940
来自专栏儿童编程

我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

14610
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.1K20
来自专栏儿童编程

天干地支五行八卦的对应关系

19090
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

27640
来自专栏儿童编程

儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

21870
来自专栏儿童编程

声音功能让儿童编程更有创造性

导读:Scratch中声音功能非常强大,除了常规的音效,你甚至可以模拟各种乐器的各个发音、设置节拍、休止……如果你愿意,甚至可以用它创作一个交响乐。我们可以引导...

13540
来自专栏儿童编程

一张图理清《梅花易数》梗概

学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

31240
来自专栏儿童编程

什么样的人生才是有意义的人生——没有标准的标准答案

【导读】其实我们可以跳出这个小圈圈去更加科客观地看一下这个世界。在夜晚的时候我们仰望天空,浩瀚的宇宙中整个地球只是一粒浮尘,何况地球上一个小小的人类?在漫长的历...

1.8K50
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

17830

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励