c/c++
- 找到单向链表中间的元素,如果有两个则取前面那个。
分析:类似于”烧绳子”问题:有一节粗细均匀的绳子,完全烧完需要10min,请设法用烧绳子的方法来计时7.5min。关键在于”速度”的控制。
本题也可借用该思想:设置快、慢指针,从头节点开始,快指针一次移动2个节点,慢指针按正常方式一次移动1个节点,大体上当快指针移动到链表尽头时,慢指针恰好位于链表中间节点。
为什么要用”大体上”,因为需要考虑几个特殊情况:链表长度小于3,此时快指针移动2个节点出问题
链表长度为奇数,快指针恰好能够移动到尾节点,此时慢节点就是中间节点
链表长度为偶数,快节点无法移动到尾节点(只能移动到尾节点前一节点),此时慢节点位于链表中间节点之一,且为前面那个
类似地,还可以倒序找出任何位置节点,比如要找倒数第k个节点,此时只需要让快节点在一开始领先于慢节点k个节点即可,只不过这种情况下,快慢指针移动速度是一样的:都是每次移动1个字节。同样地,也需要单独考虑几种特殊情况,例如链表长度小于k。
more >>