链表

September 1, 2017

链表反转

解法: 指针内存地址Hash, 快慢双指针(追及问题)

内存地址Hash的思路是将遍历过的记录存储下来, 然后把当前访问的节点与历史节点进行比较.

快慢双指针: 定义一个慢指针slow, 一个快指针fast, 慢指针走一次时快指针走两次. 根据物理知识, 如果链表有环, 快指针一定会追上慢指针. 而且快指针走的步数一定是慢指针的两倍, 因为快指针每次只能追赶一步, 追上的时候也就在一起了.

如果fast和slow中间间隔一个,则本次追不上

fast -> node2 -> slow -> node4

fast和slow相邻的时候,下次追上

fast -> slow -> node5

怎么找到环开始的点?

因为快指针走的路是慢指针的两倍, 慢指针走完一圈,恰好回到环开始的地方. 而当两个指针相遇的时候, (先假设快指针恰好多走一圈)

快慢指针同时走, 慢指针走完终点, 则快指针走完一圈再加上从开头到环入口的路才刚好走完链表的两次遍历.

所以如果快慢指针相遇时, 从链表开头到环入口的距离和相遇点到环入口的距离相等或者取模相等.