网站建设排名软件,做网站企业经营范围,怎么做一网站,郑州本地网站全文目录引言链表的中间结点题目描述与思路实现链表的倒数第k个结点题目描述与思路实现总结引言
在上一篇文章中#xff0c;介绍了反转链表 我们利用了链表是逻辑连续的特点#xff0c;逆置了链表的逻辑连接顺序#xff0c;从而实现反转链表#xff1a; 戳我查看反转链表详…
全文目录引言链表的中间结点题目描述与思路实现链表的倒数第k个结点题目描述与思路实现总结引言
在上一篇文章中介绍了反转链表 我们利用了链表是逻辑连续的特点逆置了链表的逻辑连接顺序从而实现反转链表 戳我查看反转链表详解哦
在本篇文章中我们将介绍找链表的中间结点与链表的倒数第k个结点 由于这两道题目的思路比较简单就放在一起介绍 链表的中间结点OJ链接 链表的倒数第k个结点OJ链接
链表的中间结点
题目描述与思路 这道题要求我们找到链表的中间结点并返回这个中间结点。 若链表有奇数个结点返回中间结点地址若链表有偶数个结点这个链表就有两个中间结点返回后一个。即如果单链表有5个结点返回第3个结点的地址若单链表有6个节点返回后一个中间结点即第4个结点。 函数的参数为链表第一个结点的地址。结构体变量与主函数部分已经定义我们只需要实现接口即可。
对于这道题目我们当然可以先遍历链表计算出链表的长度再运算出中间结点是第几个。然后再遍历到该位置并返回即可。 但是这样的算法显得有些麻烦有没有一种算法可以实现只遍历一遍就找到中间结点呢
当然是可以的 我们可以采用快慢指针的方法来实现快指针一次向前移动两个结点慢指针一次向前移动一个结点。当快指针到链表末尾时慢指针的位置就是单链表的中间结点
实现
为了使代码更简洁我们可以对结构体名称重命名
typedef struct ListNode ListNode;要实现这个算法我们首先需要两个指针变量fast与slow将它们都初始化为单链表头结点的地址
ListNode* fast head;
ListNode* slow head;然后while循环每次循环中slow向后移动一个结点fast向后移动两个结点。
当fast-next为NULL时即fast已经不能实现向后移动两个结点了所以此时跳出循环。并且当fast后面两个结点均不为NULL时才进行向后移动的操作否则跳出循环。每次循环先执行slow指针向后移动一个结点这样可以使链表长度为偶数时slow指向中间结点的后一个:
typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head)
{ListNode* fast head;ListNode* slow head;while (fast-next){slow slow-next;if (fast-next-next){fast fast-next-next;}else{break;}}return slow;
}链表的倒数第k个结点
题目描述与思路 这道题要求我们找到单链表中的倒数第k个结点。
我们当然可以遍历整链表计算链表的长度。计算出链表的倒数第k个元素的位置后再遍历找到并返回。 但是这样的算法显得有些麻烦我们可以尝试在只遍历一遍的情况下实现
我们可以使用双指针的方法先让快指针向后移动k个结点。然后两个指针一起向后移动当快指针t指向最后一个结点时慢指针就指向链表的倒数第k个结点。
实现
为了使代码更简洁我们可以对结构体名称重命名
typedef struct ListNode ListNode;要实现这个算法我们首先需要两个指针变量fast与slow将它们都初始化为单链表头结点的地址
ListNode* fast pListHead;
ListNode* slow pListHead;首先判断k是否为0与链表是否为空如果是则直接返回NULL
然后将fast指针向后移动k-1个结点若fast在向后移动时fast为NULL说明链表的长度小于k-1此时返回NULL。我们可以通过在循环之后对fast指针进行判断从而得知循环是否因链表长度不足而结束。
如果不是则进入循环slow指针与fast指针同时向前移动当fast指针指向链表的最后一个结点时slow指向的就是倒数第k个元素返回slow即可。 需要注意的是此时要求fast指针在链表最后一个结点时停下所以while的判断雕件为fast-nex而不是fast
typedef struct ListNode ListNode;struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{ListNode* fast pListHead;ListNode* slow pListHead;if (k 0 || pListHead NULL){return NULL;}while (--k ! 0 fast ! NULL)//--k为条件时循环k-1次{fast fast-next;}if (fast NULL){return NULL;}else{while (fast-next){slow slow-next;fast fast-next;}}return slow;
}总结
当然这只是其中一种方法相信还有别的思路。欢迎大家在评论区讨论
还有几道关于单链表的题目讲解欢迎持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出
如果本文对你有帮助希望一键三连哦
希望与大家共同进步哦
