现在的位置: 首页 > 综合 > 正文

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

2014年01月17日 ⁄ 综合 ⁄ 共 3660字 ⁄ 字号 小 中 大 ⁄ 评论关闭

转自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. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
7. 判断一个单链表中是否有环
8. 判断两个单链表是否相交
9. 求两个单链表相交的第一个节点
10. 已知一个单链表中存在环，求进入环中的第一个节点
11. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted


详细解答

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

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

[cpp] view
plaincopy

  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. 将单链表反转

从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为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.   
  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）。代码略。

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

主要思路就是使用两个指针，先让前面的指针走到正向第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.   
  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 || pAhead == NULL)     // 结点个数小于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. 查找单链表的中间结点

此题可应用于上一题类似的思想。也是设置两个指针，只不过这里是，两个指针同时向前走，前面的指针每次走两步，后面的指针每次走一步，前面的指针走到最后一个结点时，后面的指针所指结点就是中间结点，即第（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.   
  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）。参考代码如下：

自己使用栈：

[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)  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞