- 主题:一道谷歌面试题
换一种问法：一个有n个节点的单向链表，如何确定它是否存在“环”？
是不是觉得似曾相识？
答案：用两个指针，一个每次+1，另一个每次+2。如果两个指针相遇，就是有“环”
那么把指针换成一个是蚂蚁，一个是子弹。多么简单！
【 在 stub 的大作中提到: 】
: 有一个无限长的整数刻度的坐标轴，有一只蚂蚁在某一个整数刻度上，但是具体位置未知，现在蚂蚁每秒钟都会向正方向前进一格。你有一把手枪，每秒钟你能向坐标轴的某个刻度开一枪，之后只能知道打中还是没打中，请你设计一种开枪的策略，保证最终一定能打中这只蚂蚁。
--
FROM 125.33.112.*
蚂蚁>=0。当然从0开始打呀。
非要钻牛角尖吗
【 在 libgcc 的大作中提到: 】
: 这啥意思
: 如果蚂蚁在0位,每次朝前+1,你第一枪就从2开始打,每次+2
: 你永远也打不到吧
: ...................
--
FROM 106.11.34.*
你说的对。面试时会追问，如何优化？
【 在 iMx 的大作中提到: 】
: 这个不是取n次next，不是null就行了？
:
:
: ...................
--
FROM 106.11.34.*
又看了题目，你说的对。
那么就是一次打固定位置，下次打3n位置。
如果蚂蚁在固定位置负方向，就在固定位置等他送死。
如果在正方向，每次差距-1，迟早能追上（打中）
【 在 libgcc 的大作中提到: 】
: 题目不是蚂蚁位置未知吗
: 【 在 smtm 的大作中提到: 】
: : 蚂蚁>=0。当然从0开始打呀。
: ...................
--
FROM 125.33.112.*