【C++】单链表面试题
链表是非常重要的内容,在面试时也是非常喜欢问的,下面是几个常见的面试题。
说明:这些题目中的链表都是指无头单链表。
代码的实现涉及到部分C++的语法。
typedef struct Node
{
Node(const int& data)
: _data(data)
, _pNext(NULL)
{}
int _data;
Node* _pNext;
}*pNode;
- 从尾到头打印单链表
如果我们用一般的方法思考这个问题,恐怕不太好解决,如果你想到了递归,那么这道题就非常简单了。
void PrintListFromTail(pNode pHead)
{
if (pHead)
{
PrintListFromTail(pHead->_pNext);
cout << pHead->_data << " ";
}
}
当然,我们也可以用循环来解决,不过这样就要用到栈了,因为栈先进后出的特性,方便我们解决题目。
void PrintListFromTail(pNode pHead)//栈实现
{
stack<pNode> s;
pNode pCur = pHead;
while (pCur)
{
s.push(pCur);
pCur = pCur->_pNext;
}
while (!s.empty())
{
cout << s.top()->_data << " ";
s.pop();
}
}
- 删除一个无头单链表的非尾结点(不能遍历链表)
如果我们有头结点,那么这道题也就非常好做了,但是没有头结点,我们的思想是删除该结点的下一个结点,但是需要先将下一个结点的数据复制到给定的结点中,也因此,题目中说明是非尾的结点。
void DelNotTail(pNode pos)
{
assert(pos->_pNext);
pNode del = pos->_pNext;
pos->_data = del->_data;
pos->_pNext = del->_pNext;
delete del;
del = NULL;
}
- 在无头单链表的一个非头节点前插入一个结点
这道题的思路与上一个题目类似,将结点插入到给定结点的后面,然后交换两个结点的数据。
void InertFrontNode(pNode pos, int data)
{
pNode pNewNode = new Node(pos->_data);
pNewNode->_pNext = pos->_pNext;
pos->_pNext = pNewNode;
pos->_data = data;
}
- 单链表实现约瑟夫环(JosephCircle)
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到k的那个人出列;他的下一个人又从1开始报数,数到k的那个人又出列;依此规律重复下去,直到圆桌周围的人只剩下一个人。
pNode Back(pNode pHead)//返回链表的尾节点
{
pNode pCur = pHead;
while (pCur->_pNext)
pCur = pCur->_pNext;
return pCur;
}
pNode JosephCircle(pNode& pHead, int M)
{
Back(pHead)->_pNext = pHead;//将链表构成环
pNode pcur = pHead;
while (pcur->_pNext == pcur)
{
while (--M)//报数
pcur = pcur->_pNext;
pNode del = pcur->_pNext;//删结点
pcur->_pNext = del->_pNext;
pcur->_data = del->_data;
delete del;
del = NULL;
}
pcur->_pNext = NULL;
pHead = pcur;//头指针有可能改变,因此函数传引用或二级指针
return pcur;
}
- 逆置/反转单链表
注意这道题与第1个并不是一样的,此题要求逆置链表,而第1个题目只是将链表的数据域逆序打印。
void Reverse(pNode& pHead)
{
pNode pcur = pHead;
if (pcur == NULL || pcur->_pNext == NULL)
return;
pNode pNewHead = NULL;
pNode pcurnext = NULL;
while (pcur)
{
pcurnext = pcur->_pNext;
pcur->_pNext = pNewHead;
pNewHead = pcur;
pcur = pcurnext;
}
pHead = pNewHead;
}
单链表排序(冒泡排序)
void BubbleSort(pNode pHead)
{pNode pcur = pHead;
if (pcur == NULL || pcur->_pNext == NULL)
return;
pNode pTail = NULL;
pNode pcurnext = NULL;
while (pcur->_pNext != pTail)
{
while (pcur->_pNext != pTail)
{
pcurnext = pcur->_pNext;
if (pcur->_data > pcurnext->_data)
swap(pcur->_data, pcurnext->_data);
pcur = pcur->_pNext;
}
pTail = pcur;
pcur = pHead;
}
}
合并两个有序链表,合并后依然有序
pNode Merge(pNode& pHead1, pNode& pHead2)
{if (NULL == pHead1 || NULL == pHead2)
return (NULL == pHead1) ? pHead2 : pHead1;
pNode pNewHead = NULL;
pNode pTail = NULL;
pNode pcur1 = pHead1;
pNode pcur2 = pHead2;
if (pcur1->_data > pcur2->_data)
{
pNewHead = pcur2;
pTail = pNewHead;
pcur2 = pcur2->_pNext;
}
else
{
pNewHead = pcur1;
pTail = pNewHead;
pcur1 = pcur1->_pNext;
}
while (pcur1 && pcur2)
{
if (pcur1->_data > pcur2->_data)
{
pTail->_pNext = pcur2;
pcur2 = pcur2->_pNext;
pTail = pTail->_pNext;
}
else
{
pTail->_pNext = pcur1;
pcur1 = pcur1->_pNext;
pTail = pTail->_pNext;
}
}
if (pcur1 == NULL)
pTail->_pNext = pcur2;
if (pcur2 == NULL)
pTail->_pNext = pcur1;
return pNewHead;
}
当然这道题,我们也可以用递归来写。
pNode Merge(pNode& pHead1, pNode& pHead2)
{
if (NULL == pHead1 || NULL == pHead2)
return (NULL == pHead1) ? pHead2 : pHead1;
pNode pcur1 = pHead1;
pNode pcur2 = pHead2;
pNode pNewHead = NULL;
if (pcur1->_data < pcur2->_data)
{
pNewHead = pcur1;
pNewHead->_pNext = Merge(pcur1->_pNext, pcur2);
}
else
{
pNewHead = pcur2;
pNewHead->_pNext = Merge(pcur1, pcur2->_pNext);
}
return pNewHead;
}
- 查找单链表的中间节点,要求只能遍历一次链表
这道题目,我们需要定义两个指针,一个快指针一次走两步,一个慢指针一次走一步,当快指针走到尾部,慢指针则刚好走到链表中间。
pNode MidNode(pNode pHead)
{
if (pHead == NULL)
return NULL;
pNode fast = pHead;
pNode slow = pHead;
pNode midleft = NULL;
while (fast && fast->_pNext)
{
fast = fast->_pNext->_pNext;
midleft = slow;
slow = slow->_pNext;
}
return slow;//如果链表是奇数个结点,刚好返回中间的结点;如果链表是偶数个结点,返回的是中间靠右的结点;
//如果要返回偶数结点的左边,则需要加个判断链表结点个数是偶数还是奇数的条件,如果是偶数,则return midleft
}
- 查找单链表的倒数第k个节点,要求只能遍历一次链表
这道题目与上一个思路基本相似,我们可以让一个指针先走K步,然后在一起走。
pNode BackKNode(pNode pHead, size_t K)
{
if (pHead == NULL || K == 0)
return NULL;
pNode front = pHead;
pNode back = pHead;
while (K--)
{
if (front == NULL)
return NULL;
front = front->_pNext;
}
while (front)
{
front = front->_pNext;
back = back->_pNext;
}
return back;
}
删除链表的倒数第K个结点
void DelKNode(pNode* pHead, size_t K)
{//查找结点
if (pHead == NULL || K == 0)
return;
pNode front = *pHead;
pNode back = *pHead;
pNode preback = *pHead;
while (K--)
{
if (front == NULL)
return;
front = front->_pNext;
}
while (front)
{
front = front->_pNext;
preback = back;
back = back->_pNext;
}
//删除结点
if (back == *pHead)
*pHead = (*pHead)->_pNext;
else
preback->_pNext = back->_pNext;
delete back;
}
判断单链表是否带环?若带环,求环的长度?求环的入口点?
我们可以定义两个指针,一个一次走一步,一个一次走两步;如果有环的话,那么两个指针就会相遇。
pNode HasCircle(pNode pHead)//返回相遇点
{
if (NULL == pHead)
return NULL;
pNode pFast = pHead;
pNode pSlow = pHead;
while (pFast && pFast->_pNext)
{
pFast = pFast->_pNext->_pNext;
pSlow = pSlow->_pNext;
if (pFast == pSlow)
return pSlow;
}
return NULL;
}
定义一个count变量,从相遇点开始遍历环一圈。
int CircleLength(pNode pHead)
{
pNode meet = HasCircle(pHead);
if (pHead == NULL || meet == NULL)
return 0;
pNode pcur = meet;
int count = 1;
while (pcur->_pNext != meet)
{
pcur = pcur->_pNext;
count++;
}
return count;
}
pNode CircleEntry(pNode pHead)//环的入口点
{
pNode pcur = pHead;
pNode pmeet = HasCircle(pHead);
if (NULL == pHead || pmeet == NULL)
return NULL;
while (pcur != pmeet)
{
pmeet = pmeet->_pNext;
pcur = pcur->_pNext;
if (pmeet == pcur)
return pmeet;
}
return NULL;
}
- 判断两个链表是否相交,若相交,求交点。(假设链表不带环)
两个不带环的链表相交,只能是这样:
bool Is2ListCross(pNode pHead1, pNode pHead2)//判断是否相交
{
if (NULL == pHead1 || NULL == pHead2)
return false;
pNode pcur1 = pHead1;
pNode pcur2 = pHead2;
while (pcur1->_pNext)
pcur1 = pcur1->_pNext;
while (pcur2->_pNext)
pcur2 = pcur2->_pNext;
if (pcur1 == pcur2)
return true;
return false;
}
如上图所示:我们可以分别计算两个链表的结点个数,然后用大的减去小的,让较长的链表先走相减的结果步,然后在同时走,相遇的结点就是交点。
int Size(pNode pHead)//求链表结点个数
{
pNode pcur = pHead;
int count = 0;
while (pcur)
{
pcur = pcur->_pNext;
count++;
}
return count;
}
pNode CrossNode(pNode pHead1, pNode pHead2)//返回交点
{
if (!Is2ListCross(pHead1, pHead2))
return NULL;
int len1 = Size(pHead1);
int len2 = Size(pHead2);
pNode pcur1 = pHead1;
pNode pcur2 = pHead2;
int gab = len1 - len2;
if (gab >= 0)
{
while (gab--)
pcur1 = pcur1->_pNext;
}
else
{
while (gab++)
pcur2 = pcur2->_pNext;
}
while (pcur1 != pcur2)
{
pcur1 = pcur1->_pNext;
pcur2 = pcur2->_pNext;
}
return pcur1;
}
还有一种思路是,将链表的尾部连接到另一个链表的头。这样就构成了一个环,我们求环的入口点就是交点。
pNode CrossNode(pNode pHead1, pNode pHead2)//两个相交的链表 构成环,求入口点
{
if (!Is2ListCross(pHead1, pHead2))//是否相交
return NULL;
pNode pcur1 = pHead1;
while (pcur1->_pNext)
pcur1 = pcur1->_pNext;
pcur1->_pNext = pHead2;
pNode tmp = CircleEntry(pHead1);
return tmp;
}
- 判断两个链表是否相交,若相交,求交点。(假设链表可能带环)
如果两个链表可能带环,我们可以分为以下几种情况:
两个带环的链表相交只能是这两种
bool IsCrossWithCircle(pNode pHead1, pNode pHead2)//两个可能带环的链表是否相交
{
pNode pMeetNode1 = HasCircle(pHead1);//返回第一个带环链表的相遇点,如果不带环,返回NULL
pNode pMeetNode2 = HasCircle(pHead2);//返回第二个带环链表的相遇点,如果不带环,返回NULL
if (pMeetNode1==NULL && pMeetNode2==NULL)//两个链表都不带环
{
pNode pcur1 = pHead1;
pNode pcur2 = pHead2;
while (pcur1->_pNext)
pcur1 = pcur1->_pNext;
while (pcur2->_pNext)
pcur2 = pcur2->_pNext;
if (pcur1 == pcur2)
return 1;
}
else if (pMeetNode1 && pMeetNode2)//两个链表都带环
{
pNode pcur = pHead1;//第一个相遇点开始遍历环一圈,如果第二个链表的相遇点也在环上,那么两个链表相交
while (pcur->_pNext)
{
if (pcur == pMeetNode2)
return 2;
pcur = pcur->_pNext;
}
if (pcur == pMeetNode2)
return 2;
}
return false;
}
从第一个链表的相遇点断开环,记录相遇点的下一个结点,将相遇点连接到第二个链表的头,相当于求链表环的入口点,最后再将链表恢复原样。
如图所示:
除此之外,我们还可以求出环的入口点,这样从链表头部到环入口点可以看成求两个不带环的链表的交点
pNode CrossNodeWithCircle(pNode pHead1, pNode pHead2)//两个带环的链表相交,返回交点
{
pNode pMeetNode1 = HasCircle(pHead1);
pNode pMeetNode2 = HasCircle(pHead2);
pNode tmp = pMeetNode1->_pNext;//第一个链表相遇点的下一个结点
if (pMeetNode1 && pMeetNode2)//两个链表都带环
{
pMeetNode1->_pNext = pHead2;
pNode CrossNode = CircleEntry(pHead1);
pMeetNode1->_pNext = tmp;//恢复原链表
return CrossNode;
}
return NULL;
}
复杂链表的复制。一个链表的每个节点,有一个指向next指针指向下一个节点,还有一个random指针指向这个链表中的一个随机节点或者NULL,现在要求实现复制这个链表,返回复制后的新链表。
typedef struct Node
{Node(const int& data)
: _data(data)
, _pNext(NULL)
, _pRomdon(NULL)
{}
int _data;
Node* _pNext;
Node* _pRomdon;
}*pNode;
复杂链表的复制可以分为三个步骤:
第一步:将原链表的每一个结点都复制一份,然后连接在一起。如图所示:绿色为随机指针的连接,黑色为Next指针的指向。
第二步:处理链表底下一排的新链表的随机指针的连接。pnew->_pRomdon = pold->_pRomdon->_pNext;
第三步:将新链表分离出来
pNode ComplexListCopy(pNode pHead)
{
if (NULL == pHead)
return NULL;
pNode pold = pHead;
while (pold)//复制结点
{
pNode pNewNode = new Node(pold->_data);
pNewNode->_pNext = pold->_pNext;
pold->_pNext = pNewNode;
pold = pold->_pNext->_pNext;
}
pold = pHead;//指向随机指针
pNode pnew = pold->_pNext;
while (pold)
{
if (NULL != pold->_pRomdon)
pnew->_pRomdon = pold->_pRomdon->_pNext;
pold = pnew->_pNext;
if (pold != NULL)
pnew = pold->_pNext;
}
pold = pHead;
pnew = pold->_pNext;
pNode pcur = pnew;
while (pnew->_pNext)//分离
{
pold->_pNext = pnew->_pNext;
pold = pnew->_pNext;
pnew->_pNext = pold->_pNext;
pnew = pnew->_pNext;
}
return pcur;
}
还没有评论,来说两句吧...