单链表基础操作可以参见我的另一篇博客：建议从基础到进阶
? ? ? ?单链表(面试算法题1)---学习链表的关键在于code
面试精要：对于部分问题会给出多种解决方案【在时间复杂度相同的情况下优化空间复杂度】
【在我们设计一个算法的时候，优先考虑时间复杂度最优。在时间复杂度相同的情况下再去优化空间复杂度】
今天我们探讨快慢指针在单链表中的四个经典问题(容易搞错)：
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;
}????????????????