关于链表面试题的一些理解

本是古典何须时尚 2022-08-23 08:49 84阅读 0赞

#  面试题一.删除无头单链表的非尾结点 #

# Del\_Nottail(pLinkNode pos); #

顾名思义删除非尾结点就是删除的结点不是最后一个结点，之前在实现链表功能的时候就有一个函数是 Erase\_LInkList 它的功能就是在链表中删除指定位置的结点，乍一看这两个函数没有什仫区别可是仔细看就会发现我们要实现的函数功能没有给出头指针啊？这可怎仫办？我们知道要删除一个结点如果传过来头指针那就好办了：只要遍历链表就可以了，通过记住要删除结点的前一个结点，再将这个结点的指针域指向要删除结点的后一个结点，最后将要删除的结点释放就达成目标啦！如果没有传过来头指针呢？如果此时我们还用之前那种遍历的思路就会进入误区，首先并没有头指针给我们去遍历啊？此时我们是不是可以通过交换的方式呢？当然可以啦！在这里我总结为四步删除无头单链表的非尾结点：

1).建立指向结点的指针del，该指针指向要删除结点的下一个结点；

2).将要删除结点的数据域修改为下一个结点的数据；

3).将要删除结点的指针域修改为下下一个结点的地址；

4).释放del结点指针删除该结点；

代码实现如下：

void Del_Nottail(pLinkNode pos)          //删除无头单链表的非尾结点
    {
    	pLinkNode del=pos->next;
    	assert(pos != NULL);
    	pos->data=pos->next->data;
    	pos->next=pos->next->next;
    	free(del);
    	del=NULL;
    }

那仫代码是不是可以达到我们想要的结果呢？如果有一个单链表它的原始数据为1->2->3->4->5->over，此时我们删除其中的一个非尾结点是不是可以达到目标呢？请看如下结果：

![Center][]

看3被删除了吧！如果我们不小心删除的是尾结点也就是最后一个结点呢？请看下图：

![Center 1][]

看程序奔溃了吧！其实这正是达到了我们的目的，因为我们知道这道面试题的功能就是删除非尾结点，你删除了尾结点程序当然会奔溃了啊！当然现实中这种问题最好不要出现，因为当程序奔溃了人们自然想到程序出了问题，但是实际上呢？程序确实没有问题，这是不是让人纠结又郁闷，所以最好避免这种问题的出现.在断言时也要断言pos->next,下面我们来看一道和它相关的链表面试题吧！

面试题二.删除倒数第k个结点，只允许遍历一遍链表

Del\_KNode(pLinkList plist,DataType k);

既然要删除倒数第k个结点首先我们要找到这个倒数第k个结点然后删除.那仫如何去寻找呢？在这里我提供一种思路：创建两个指针都指向单链表的第一个结点，使得后指针先不动，前指针先指向正数第k个结点，此时两个指针一起移动，直到前指针为NULL，此时后指针指向的就是倒数第k个结点啦！ 这就有点快慢指针的味道了，有兴趣的同学可以自己下去画图理解；

接下来的问题就是如何删除这个倒数第k个结点呢？如果我们使用 Erase\_LinkList 的方法是不是也可以删除第一个结点呢？我们知道Erase\_LinkList 它的思路就是要记住要删除结点的前一个结点，如果使用这种思路正如之前所说的要是删除第一个结点那仫它的前一个结点是什仫呢？自然是找不到的啦~~~~如果我们采用面试题一的方法呢？具体分析见面试题一，此时不论要删除的是链表的哪一个结点都是可以删除的啦~~~~~

void Del_KNode(pLinkList plist,DataType k)        //删除倒数第k个结点(只允许遍历一遍链表) 
    {
    	pLinkNode front=NULL;
    	pLinkNode back=NULL;
    	pLinkNode del=NULL;
    	assert(plist);
    	front=plist->phead;
    	back=plist->phead;
    	if(NULL == plist->phead)   //空链表
    	{
    		return ;
    	}
    	else
    	{
    		while(front)   //back指向倒数第k个结点
    		{
    			k--;
    			if(k < 0)
    			{
    				back=back->next;
    			}
    			front=front->next;
    		}
    	}
    	if(k <= 0)   //删除back所指向的结点，借用Del_Nottail函数的方法
    	{
    		Del_Nottail(back);   
    		//back->data=back->next->data;   //Del_Nottail的具体实现方法
    		//del=back->next;
    		//back->next=del->next;
    		//free(del);
    		//del=NULL;
    	}
    }

普通的情况：删除不是第一个结点的结点

![Center 2][]

特殊的情况：删除第一个结点：

![Center 3][]

~~~~

面试题三.查找链表的中间结点（只允许遍历一遍链表）

pLinkNode Find\_MidNode(pLinkList plist);

拿到这道问题我刚开始的想法就是如果能先遍历一遍链表统计得到链表的总结点数，然后再次遍历链表每当遍历一个结点统计个数就加1直到和刚开始的总结点数/2相等，此时指针所指向的结点就是链表的中间结点；但是这种想法遍历了两遍链表并没有满足题意~~~

如果要满足题意应该如何去做呢？在面试题二中我们在找倒数第K个结点时影影约约感觉到了快慢指针的身影，那仫如何用快慢指针的思路去解决查找链表的中间结点问题呢？当然我们可以设置两个指针快指针，慢指针，快指针每次走两步，慢指针每次只走一步，当快指针指向NULL时慢指针就指向的是链表的中间结点啦~此时还存在一个问题如果单链表的结点个数是偶数呢？那仫我们返回前一个结点还是后一个结点呢？按理说两个应该都可以的，关键看代码如何编辑了：

pLinkNode Find_MidNode(pLinkList plist)          //查找链表的中间结点(只允许遍历一遍链表)
    //快慢指针的问题
    {
    	pLinkNode fast=NULL;
    	pLinkNode slow=NULL;
    	assert(plist);
    	fast=plist->phead;
    	slow=plist->phead;
    	while(fast != NULL && fast->next->next != NULL)
    		//如果链表是偶数，判断条件为:fast->next->next则找到的前一个中间结点，
    		//若判断条件为:fast->next,则找到的是后一个中间结点
    	{
    		fast=fast->next->next;
    		slow=slow->next;
    	}
    	return slow;
    }

返回前一个中间结点：

![Center 4][]

返回后一个中间结点：

![Center 5][]

面试题四.逆序单链表

void Reverse\_list(pLinkList plist);

看到逆序这两个字相信大家都不会陌生的，在之前我们逆序字符串和整形数组的时候，我们的想法就是两个指针一个指向第一个元素，一个指向最后一个元素，只要两个指针不相遇，我们就交换两个指针指向的内容；这样的想法是不是可以化用到链表中去呢？我们可以很轻松的找到链表的尾结点，需要注意的是给出的是单链表：只允许从前往后遍历，不允许从后往前遍历.如果给出的是双向循环链表这样的思路就可以尝试了，此时却是万万不可以的；

那仫如何逆序链表呢？此时我们需要设置新的头指针了，下面我总结了逆序链表的四步曲：~~

1).tmp保存结点~cur指向下一个结点~

2).tmp指向新的头指针~如果是第一个结点，刚开始的头指针为NULL，即tmp->next=NULL~

3).新的头结点向后移动，指向tmp~

4).逆序完成后要更新头指针~

void Reverse_list(pLinkList plist)       //逆序链表
    {
    	pLinkNode newhead=NULL;
    	pLinkNode tmp=NULL;
    	pLinkNode cur=NULL;
    	assert(plist);
    	cur=plist->phead;
    	while(cur != NULL)
    	{
    		tmp=cur;
    		cur=cur->next;
    		tmp->next=newhead;
    		newhead=tmp;
    	}
    	plist->phead=newhead;   //更新头
    }

![Center 6][]

面试题五.在当前结点前插入一个结点(无头单链表)

void Insert\_FrontNode(pLinkNode pos,DataType x);

这单题类似于我们之前实现的链表功能Insert\_Front 唯一的区别就是此面试题没有传递过来头指针也就是说是不允许遍历链表的，那仫如何删除呢？方法类似面试题1，先为数据x开辟结点空间将该结点连接到当前结点pos之后，看到这里大家或许会疑惑，题目不是要求插入到当前结点pos之前吗？你插入到结点后面能达到目标吗？我们知道题目中并没有给出头指针我们是不可能找到要插入结点的前一个结点的，可是我们将新结点插入到当前结点的后面就满足题意了吗？别着急，先连接起来，接下来我们将当前结点pos数据域和新结点的数据域交换不就可以了吗？不信？？？你继续向后看~~~~

void Insert_FrontNode(pLinkNode pos,DataType x)   //无头单链表前插入一个结点
    {
    	pLinkNode newNode=NULL;
    	DataType tmp=0;
    	assert(pos != NULL);
    	newNode=Create_Node(x);
    	newNode->next=pos->next;
    	pos->next=newNode;
    	tmp=newNode->data;
    	newNode->data=pos->data;
    	pos->data=tmp;
    }

我们是在数据域为3的结点前面插入结点数据域为6的结点：

![Center 7][]

相信自己你就是最棒的！！！

[Center]: /images/20220721/efb0d6ec25b749379ab4574ea25287f3.png
[Center 1]: /images/20220721/17bc56d7c9804557a90e0d1c3ef6fac4.png
[Center 2]: /images/20220721/04a1eaf8cb2246e29f29307d2ffc2b19.png
[Center 3]: /images/20220721/08ab85b0eddf4d63a2cf8a7025bf5fc7.png
[Center 4]: /images/20220721/23d3d467bbec448693b7308d60159487.png
[Center 5]: /images/20220721/7e71f65db09747f38c25b859119b44e2.png
[Center 6]: /images/20220721/a031df8fc05d4013b6462903ada2a6cb.png
[Center 7]: /images/20220721/400c33ad5a824ba0ad1b45402b1d139a.png