这种链表的题,找第几个结点,有个很骚的解法,就是用计数器找到那个结点,但是感觉完全避开了他想考察的算法。这种题应该要能熟练使用快慢指针这种算法。
这种算法就根据题目来一边分析一边介绍其用处
根据题目
要寻找中间的结点,如果是有两个中间结点,就返回第二个结点。
通常是设置一个快指针,一个慢指针。而快指针的速度是慢指针的两倍。也就是每次快指针一次走两个元素,而慢指针一次走一个元素。
它要找中间结点。
初始时
移动
再移动
这一步就已经达到目的了,慢指针移动到了中间结点,而此时,循环应该已经结束了,而快指针则是到了最后一个元素,这应该是一个循环结束的条件。
当有两个中间结点时。
移动
移动,慢指针已经到了第一个中间结点,再移动一次就可以到达第二个中间结点。
这种情况下, 快指针应该是走到了最后一个指针的next时,才结束循环移动。
一种是当快指针移动到最后一个结点时,循环结束,
一种是当快指针移动到最后一个结点的next时才结束循环。
总结一下条件是
fast==NULL结束条件对应有两个中间结点的情况,
fast->next == NULL,是对应只有一个中间结点的情况。
无论哪种情况,都是快指针走两个结点,慢指针走一个结点。
当循环遇到两个条件中的y一个都要结束循环,返回慢指针
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
再来看看利用快慢指针的另一道题
这就比较不太一样。这是规定好特定的结点。但我们结束快指针移动到最后一个结点或NULL时结束,也就是说,当快指针移动到末尾时,慢指针要正好移动到到数第K个结点。
意味着,快指针于慢指针相差K个结点。
可以让快指针先走K个结点,再快慢指针一起走,当结束时,正好在倒数第K个结点处。
先走K个结点
再两指针一起走
继续
继续
最后一步
因为是倒数第K个快指针如果再最后一个结点,那么慢指针与快指针相差两个结点,就是倒数第3个结点,所以快指针要在NULL时,才满足。
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
struct ListNode* fast=head;
struct ListNode* slow=head;
for(int i=0;i<k;i++)
{
if(fast==NULL)
return NULL;
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
上面都是常规情况,但是还有一些比较奇怪的测试用例。
比如k会超过链表的结点数,那就只能在快指针达到NULL是就提前结束。
或者本身就是一个空链表,那就也是直接结束。
快慢指针感觉挺巧妙的,可以好好理解使用。
前言 复用,是一个重要的话题,也是我们日常开发中经常遇到的,不可避免的问题。...
关于Jmeter性能测试工具不再过多介绍。如果你要学习软件性能测试,那么多少应该...
Erlang 是一种用于构建大规模可扩展实时系统的函数式编程语言。Erlang 最初是由 ...
接上一篇: 正则表达式(regex)错误使用导致功能漏洞 ,我们继续梳理,正则表达...
van-uploader v-model="fileList" multiple :after-read="afterRead" :max-count...
步骤 首选项 Editor General 如下图,勾...
本文实例讲述了JS和C#实现的两个正则替换功能。分享给大家供大家参考,具体如下...
正则表达式对于Python来说并不是独有的,最近在把google搜索的结果中所有的站点...
? 近期ARMv9架构发布根据安谋官方的说法最新V9版本的ARM芯片具有安全计算、SVE2...
git push时终端报错: error: RPC failed; HTTP 413 curl 22 The requested URL ...