单链表基础操作可以参见我的另一篇博客：建议从基础到进阶
面试精要：对于部分问题会给出多种解决方案【在时间复杂度相同的情况下优化空间复杂度】
【在我们设计一个算法的时候，优先考虑时间复杂度最优。在时间复杂度相同的情况下再去优化空间复杂度】
今天我们探讨快慢指针在单链表中的四个经典问题(容易搞错)：
1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
Les's go go go!
==》以上四个问题的模式是相同的，都是通过一个快指针fast和一个慢指针slow来找找中点。
每一步fast眺两格，slow跳一格。当fast不满足跳两格的条件是，此时slow到达中点。
【举例理解：小明和小明他爸同一时刻同从同一个起点出发，小明他爸每次都走的距离为小明的两倍。假设这段路程的总长度是length,则当小明他爸走到终点的时候，小明在什么位置。很明显小明走了length/2的路程，处在中点的位置】
现在我们问题的模式搞懂了，要根据题目的不同条件来相应的初始位置。
【为了简化问题，我们不妨先将返回头节点的情况单独拎出来，预先做处理】
问题1：奇数返回中点，偶数返回上中点。
返回头节点的情况:链表为空 、只有一个节点的链表 、只有两个节点的链表
处理完这个之后，我们就直到这个链表一定有大于等于三的节点。所以我们可以将slow和fast初始化为：
附上代码：
//链表的基本在文章开头的博客链接中已经有了,不清楚的可以先阅读那篇内容 Node midOrUpMidNode(Node head){ //先处理返回头节点的情况 if(head == NULL || head->next == NULL || head->next->next == NULL){ return head; } //其它情况 Node slow = head->next; Node fast = head->next->next; while(fast->next != NULL && fast->next->next != NULL){ slow = slow->next; fast = fast->next->next; } return slow; }
问题2：奇数返回中点，偶数返回下中点。
我们来对比问题1的情况，奇数情况下是一样的，偶数情况下不同。问题2返回偶数的情况是问题1返回的下一个节点。所以问题解决了。显然，我们可以在之前做处理，也可以在之后在处理。
Node midOrDownMidNode(Node head){ if(head==NULL || head->next==NULL){ retrun head; } Node slow = head->next; Node fast = head->next; while(fast->next==NULL && fast->next->next==NULL){ fast=fast->next->next; slow=slow->next; } return slow }
问题3：与问题1类似，但是需要多考虑一个条件就是返回为NULL的情况。
当只有一个结点或者两个结点的时候，返回为NULL。
其它情况只是将问题1的返回往前退了一步。
Node midOrUpMidPreNode(Node head){ if(head==NULL || head->next==NULL || head->next->next==NULL){ return NULL; } Node slow = head; Node fast = head->next->next; while(fast->next!=NULL && fast->next->next!=NULL){ slow = slow->next; fast = fast->next->next; } return slow; }
问题4：奇数长度返回中点前一个，偶数长度返回下中点前一个
与问题2类似，不过要考虑返回NULL的情况。
只有一个结点是返回为NULL
其它情况返回都是问题2的返回的前一个结点。
Node midOrDownMidPreNode(Node head){ if(head == NULL || head->next==NULL){ return NULL; } if(head->next->next == NULL){ return head; } Node slow = head; Node fast = head->next; while(fast->next != NULL && fast->next->next != NULL){ slow = slow->next; fast = fast->next->next; } return slow; }
