快慢指针巧解链表中间结点

今天我们学习的是力扣上第876道算法题:链表的中间结点。小编依旧会以图文并茂的方式来进行讲解。这道算法题会用到一个特别神奇的算法思想:快慢指针法。希望能给大家带来一些收获。

一、原题重现

这道算法题描述的也非常简单就是找中间那个结点。分两种情况如果结点个数是单数就直接找中间的那个就行，如果是双数就找第二个中间结点。接下来小编会依次为大家讲解。

二、快慢指针

在文章开头小编提到了快慢指针这个算法思想，小编简单的为大家介绍一下。快慢指针顾名思义就是有两个指针：一个跑的快，一个跑的慢。

快指针一下子跑两个结点 慢指针一下子就跑一个指点。为什么要这么去使用呢 ？我们从题里面去慢慢领悟。

三、题目讲解

我们先来看第一种情况 有奇数个结点。

这里我们定义两个指针 一个快指针(fast) 一个慢指针(slow)。起始时让他们都指向头结点，接下来就让他们循环走下去就好。

走到这里相信大家已经发现了当fast->next指针等于NULL时 low指针恰好就停在我们想要的中间指针这个位置。 此时我们只要返回low指针就好啦。 接下来我们模拟实现有偶数个结点的情况。

相同的部分小编就不一一介绍啦。唯一需要特别强调的是看fast指针走到5的这个时候，此时fast->next指针就不等于NULL.如果fast指针再走两步是不是就越过6跳到6后面的那个结点了。

此时我们只要把fast指针设成空指针 low指针就能恰好到我们想要的位置。

到这里我们已经将两种情况都已经分析完了，循环条件我们也分析出来了只要fast&&fast->next二者都不为NULL就继续循环 有一个为NULL就停止循环。

四、代码展示

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { ListNode*fast=head; ListNode*low=head; while(fast&&fast->next) { fast=fast->next->next; low=low->next; } return low; }

此次的分享就到此结束啦。希望大家都能掌握快慢指针这个算法，未来的算法题还会用上。希望能给大家带来一些启发~