问题准备知识：
链表有三种：单向、双向、循环。
对于一个单链表，只能从链表的一段开始遍历，对于双链表，可以两端同时开始。
问题：如何在一次传递中找到长度未知的单链表的中间元素？
链表中间元素含义：索引为最中间值得哪个元素，奇数为最中间，偶数有两个。
一次传递：一次遍历。
开始思考这个问题时候这样想的：中间元素也就是索引值是整个链表长度的一半，那么必然知道索引长度才能确定中间索引的值，毕竟中间索引值是链表长度的一个函数值。那么无论如何最终都必须得到链表的长度值。
类似一个问题是这样。已知一条绳子，在不知绳子长度情况下如何求得绳子一半的长度。对折绳子可以确定绳子一半长度未知，但是无法确定绳子具体一般长度是多少，也就是多少厘米。但仔细想想，所谓具体多少厘米，实际上也是一种相对长度的表示，它表示相对国际标准长度对应那个物体尺寸的倍数。
题目里面是向确定中间索引位置，但是中间索引实际上是不需要确定具体索引值，就像确定绳子中间长度位置一样，这个不由绳子本身具体长度决定，而仅仅和自己有关。用其他具体值来表示的长度是引用外界的长度定义方式来衡量。
所以此题思考方式也是不求出链表根据外界的衡量方式确定的度量长度，而是根据自身。
设置两个指针，其中指针A遍历速度是指针B遍历速度的两倍。
他们同事从同一个起点（链表头）开始遍历。当A到达链表尾部，也就是结束位置时候，B移动距离是A 的一半，也即是刚到链表中间位置。此时B所在节点就是中间位置。
主要思路确定后，细节处理：
什么时候是A指针的结束位置：
当链表长度为偶数：A指针在链表最后一位，后面没节点。此时有两个中间元素；
当链表长度为奇数，A指针最后一位后面还有一个节点。此时有一个索引元素。
网友评论