转自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
详细解答
这是最最基本的了,应该能够迅速写出正确的代码,注意检查链表是否为空。时间复杂度为O(n)。参考代码如下:
- // 求单链表中结点的个数
- unsigned int GetListLength(ListNode * pHead)
- {
- if(pHead == NULL)
- return 0;
- unsigned int nLength = 0;
- ListNode * pCurrent = pHead;
- while(pCurrent != NULL)
- {
- nLength++;
- pCurrent = pCurrent->m_pNext;
- }
- return nLength;
- }
从头到尾遍历原链表,每遍历一个结点,将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O(n)。参考代码如下:
- // 反转单链表
- ListNode * ReverseList(ListNode * pHead)
- {
- // 如果链表为空或只有一个结点,无需反转,直接返回原链表头指针
- if(pHead == NULL || pHead->m_pNext == NULL)
- return pHead;
- ListNode * pReversedHead = NULL; // 反转后的新链表头指针,初始为NULL
- ListNode * pCurrent = pHead;
- while(pCurrent != NULL)
- {
- ListNode * pTemp = pCurrent;
- pCurrent = pCurrent->m_pNext;
- pTemp->m_pNext = pReversedHead; // 将当前结点摘下,插入新链表的最前端
- pReversedHead = pTemp;
- }
- return pReversedHead;
- }
最普遍的方法是,先统计单链表中结点的个数,然后再找到第(n-k)个结点。注意链表为空,k为0,k为1,k大于链表中节点个数时的情况。时间复杂度为O(n)。代码略。
这里主要讲一下另一个思路,这种思路在其他题目中也会有应用。
主要思路就是使用两个指针,先让前面的指针走到正向第k个结点,这样前后两个指针的距离差是k-1,之后前后两个指针一起向前走,前面的指针走到最后一个结点时,后面指针所指结点就是倒数第k个结点。
参考代码如下:
- // 查找单链表中倒数第K个结点
- ListNode * RGetKthNode(ListNode * pHead, unsigned int k) // 函数名前面的R代表反向
- {
- if(k == 0 || pHead == NULL) // 这里k的计数是从1开始的,若k为0或链表为空返回NULL
- return NULL;
- ListNode * pAhead = pHead;
- ListNode * pBehind = pHead;
- while(k > 1 && pAhead != NULL) // 前面的指针先走到正向第k个结点
- {
- pAhead = pAhead->m_pNext;
- k--;
- }
- if(k > 1 || pAhead == NULL) // 结点个数小于k,返回NULL
- return NULL;
- while(pAhead->m_pNext != NULL) // 前后两个指针一起向前走,直到前面的指针指向最后一个结点
- {
- pBehind = pBehind->m_pNext;
- pAhead = pAhead->m_pNext;
- }
- return pBehind; // 后面的指针所指结点就是倒数第k个结点
- }
此题可应用于上一题类似的思想。也是设置两个指针,只不过这里是,两个指针同时向前走,前面的指针每次走两步,后面的指针每次走一步,前面的指针走到最后一个结点时,后面的指针所指结点就是中间结点,即第(n/2+1)个结点。注意链表为空,链表结点个数为1和2的情况。时间复杂度O(n)。参考代码如下:
- // 获取单链表中间结点,若链表长度为n(n>0),则返回第n/2+1个结点
- ListNode * GetMiddleNode(ListNode * pHead)
- {
- if(pHead == NULL || pHead->m_pNext == NULL) // 链表为空或只有一个结点,返回头指针
- return pHead;
- ListNode * pAhead = pHead;
- ListNode * pBehind = pHead;
- while(pAhead->m_pNext != NULL) // 前面指针每次走两步,直到指向最后一个结点,后面指针每次走一步
- {
- pAhead = pAhead->m_pNext;
- pBehind = pBehind->m_pNext;
- if(pAhead->m_pNext != NULL)
- pAhead = pAhead->m_pNext;
- }
- return pBehind; // 后面的指针所指结点即为中间结点
- }
对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系统使用栈,也就是递归。注意链表为空的情况。时间复杂度为O(n)。参考代码如下:
自己使用栈:
- // 从尾到头打印链表,使用栈
- void RPrintList(ListNode * pHead)
- {
- std::stack<ListNode *> s;
- ListNode * pNode = pHead;
- while(pNode != NULL)
- {
- s.push(pNode);
- pNode = pNode->m_pNext;
- }
- while(!s.empty())
- {
- pNode = s.top();
- printf("%d\t", pNode->m_nKey);
- s.pop();
- }
- }
使用递归函数:
- // 从尾到头打印链表,使用递归
- void RPrintList(ListNode * pHead)
- {
- if(pHead == NULL)