【C++】单链表面试题

我就是我 2022-06-06 14:16 217阅读 0赞

链表是非常重要的内容，在面试时也是非常喜欢问的，下面是几个常见的面试题。

说明：这些题目中的链表都是指无头单链表。

代码的实现涉及到部分C++的语法。

typedef struct Node
    {
    	Node(const int& data)
    	: _data(data)
    	, _pNext(NULL)
    	{}
    	int _data;
    	Node* _pNext;
    }*pNode;

1. 从尾到头打印单链表

如果我们用一般的方法思考这个问题，恐怕不太好解决，如果你想到了递归，那么这道题就非常简单了。

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();
    	}
    }

2. 删除一个无头单链表的非尾结点（不能遍历链表）

如果我们有头结点，那么这道题也就非常好做了，但是没有头结点，我们的思想是删除该结点的下一个结点，但是需要先将下一个结点的数据复制到给定的结点中，也因此，题目中说明是非尾的结点。

void DelNotTail(pNode pos)
    {
    	assert(pos->_pNext);
    	pNode del = pos->_pNext;
    	pos->_data = del->_data;
    	pos->_pNext = del->_pNext;
    	delete del;
    	del = NULL;
    }

3. 在无头单链表的一个非头节点前插入一个结点

这道题的思路与上一个题目类似，将结点插入到给定结点的后面，然后交换两个结点的数据。

void InertFrontNode(pNode pos, int data)
    {
    	pNode pNewNode = new Node(pos->_data);
    	pNewNode->_pNext = pos->_pNext;
    	pos->_pNext = pNewNode;
    	
    	pos->_data = data;
    }

4. 单链表实现约瑟夫环(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;
    }

5. 逆置/反转单链表

注意这道题与第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;
    }

6. 单链表排序（冒泡排序）

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

7. 合并两个有序链表,合并后依然有序

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

8. 查找单链表的中间节点，要求只能遍历一次链表

这道题目，我们需要定义两个指针，一个快指针一次走两步，一个慢指针一次走一步，当快指针走到尾部，慢指针则刚好走到链表中间。

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
    }

9. 查找单链表的倒数第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;
    }

10. 删除链表的倒数第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;
    }

11. 判断单链表是否带环？若带环，求环的长度？求环的入口点？

我们可以定义两个指针，一个一次走一步，一个一次走两步；如果有环的话，那么两个指针就会相遇。

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

![SouthEast][]

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

12. 判断两个链表是否相交，若相交，求交点。（假设链表不带环）

两个不带环的链表相交，只能是这样：

![SouthEast 1][]

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

13. 判断两个链表是否相交，若相交，求交点。（假设链表可能带环）

如果两个链表可能带环，我们可以分为以下几种情况：

![SouthEast 2][]

两个带环的链表相交只能是这两种

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

从第一个链表的相遇点断开环，记录相遇点的下一个结点，将相遇点连接到第二个链表的头，相当于求链表环的入口点，最后再将链表恢复原样。

如图所示：

![SouthEast 3][]

除此之外，我们还可以求出环的入口点，这样从链表头部到环入口点可以看成求两个不带环的链表的交点

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

14. 复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。

typedef struct Node
    {
    	Node(const int& data)
    	: _data(data)
    	, _pNext(NULL)
    	, _pRomdon(NULL)
    	{}
    	int _data;
    	Node* _pNext;
    	Node* _pRomdon;
    }*pNode;

复杂链表的复制可以分为三个步骤：

第一步：将原链表的每一个结点都复制一份，然后连接在一起。如图所示：绿色为随机指针的连接，黑色为Next指针的指向。

![SouthEast 4][]

第二步：处理链表底下一排的新链表的随机指针的连接。pnew->\_pRomdon = pold->\_pRomdon->\_pNext;  
![SouthEast 5][]

第三步：将新链表分离出来  
![SouthEast 6][]

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

[SouthEast]: /images/20220606/c4348eaad58944428d00799af8aa3caa.png
[SouthEast 1]: /images/20220606/e310cafcd56e4acba8d327e826ba7a6a.png
[SouthEast 2]: /images/20220606/c048a65f6de544bca46f016f9b8b175a.png
[SouthEast 3]: /images/20220606/1a23dc245b5745f79f2eac50feab627e.png
[SouthEast 4]: /images/20220606/ef6060c23783481896f925007bd73373.png
[SouthEast 5]: /images/20220606/cb6a97d5bfb34ed081051e772c87e942.png
[SouthEast 6]: /images/20220606/2c22e6f4408d4c15847a4d059f8b30ab.png