一、问题描述
二、解题思路
1.计数器方式
实现比较简单，但效率相对较低
- 首先创建一个遍历链表的指针和一个计数器变量
- 第一次遍历链表，求得链表长度
- 然后指针回到链表初始位置，计数器/2
- 第二次遍历链表，找到对应位数的节点的地址
- 返回找到的节点地址
通过计数器/2获得的位置
- 当链表为奇数个节点时，得到的是中间节点的位置
- 当链表有偶数个节点时，得到的是中间第二个节点的位置
- 当链表为空时，得到初始位置，即NULL
所以，无论何种情况都可以得到正确的结果
2.快慢指针方式
对逻辑和细节要求比较高，效率高
- 创建两个快慢指针，初始都指向链表的首节点
- 遍历链表，循环执行的条件是fast不为空
- 慢指针每次向后一个节点，快指针移动两个节点
- 奇数个元素的链表，fast指针最终会落在最后一个节点上，此时slow指向的节点即为中间节点
- 偶数个元素的链表，fast指针最终会落在最后一个节点后面的NULL，此时slow指向的节点即为中间节点的第二个节点
- 返回slow指针指向的地址
奇数个元素的链表的执行逻辑
1.初始状态，快慢指针都指向第一个节点
2.快慢指针各执行一次移动操作后
3.当fast->next为NULL时，不能继续移动，此时slow指针指向的就是中间节点
偶数个元素的链表的执行逻辑
1.初始状态，快慢指针都指向第一个节点
2.快慢指针各执行一次移动操作后
3.快慢指针再执行一次移动操作后
4.当fast为NULL时，不能继续移动，此时slow指针指向的就是中间节点
三、源代码实现
1.计数器方式
struct ListNode* middleNode1(struct ListNode* head) //计数器方式 { struct ListNode* pcur = head;//遍历链表的指针 int count = 0; while (pcur)//第一次遍历链表，求得链表长度 { pcur = pcur->next; count++; } count /= 2;//长度/2求得中间节点在第几位 pcur = head;//指针回到初始位置 while (count)//第二次遍历链表，找到对应位数的节点的地址 { pcur = pcur->next; count--; } return pcur;//如果链表为空，此处可以正确返回NULL }
2.快慢指针方式
struct ListNode* middleNode2(struct ListNode* head) { struct ListNode*slow,*fast;//创建快慢指针 slow=fast=head;//初始化 while(fast&&fast->next)//当快指针可以移动两步时执行循环 { slow=slow->next;//慢指针走一步 fast=fast->next->next;//快指针走两步 } return slow;//遍历完成时，slow所指节点就是中间节点 }
注意
while(fast&&fast->next)中的fast 与fast->next语句不可以调换顺序
当链表有偶数个节点时，fast最后一次会走到NULL，fast->next对空指针解引用会报错
而当先判断fast已经为空时，因为逻辑运算符的短路问题，后面的fast->next语句不会再执行
关于短路问题更多细节可以参考C语言逻辑运算符的短路问题
