一、题目
给定一个长度大于1的单链表，如何遍历一次获取到中间节点的值 注：如果链表长度为偶数，则结果去中间两个节点中的第一个
输入、输出描述
输入：
list: 长度大于1的单链表
输出：
中间节点的值
Example
输入：
list=[2,6,8,4,1]
输出：
8
二、思路
使用一快一慢两个指针同时遍历链表，快指针每次往前走两步，慢指针每次走一步，当快指针遍历完后，慢指针相应走了一半长度， 此时慢指针所指的节点即为中间节点。
双指针单链表遍历常用的手段，以下拓展题目都用到了双指针方法。
拓展：
（1）查找链表的第 len(list)/N 个节点
慢指针每次走一步，快指针每次走len(list)/N步，当快指针走完时，慢指针所指向的节点即为目标节点
（2）查找链表的倒数第K个节点
快指针先走k步，然后两个指针同时往后走，每次走一步，当快指针走完时，慢指针自然走到了倒数第k个节点。
（3）判断单链表是否存在换
慢指针每次走一步，快指针每次走两步，如果不存在环，快慢指针不可能相遇，如果存在环则两个指针一定会相遇（why，这个我们后面一期专门分析）。
欢迎评论区留言补充更多案例
三、代码
class LinkNode<T> {
public T data;
public LinkNode<T> next;
}
public int solution(LinkNode<Integer> head) {
LinkNode<Integer> pFast = head;
LinkNode<Integer> pSlow = head;
if (pFast.next != null) {
pFast = pFast.next;
}
while (pFast != null && pFast.next != null) {
pSlow = pSlow.next;
pFast = pFast.next;
if (pFast != null) {
pFast = pFast.next;
}
}
return pSlow.data;
}
个人资料
推荐圈子
上一篇：
Pandas教程--Series
下一篇：线程池
猜你感兴趣的圈子：
标签： pfast、指针、linknode、pslow、当快、面试题
