最后解释一遍快慢指针法解带圈链表问题 « Ashes of Time
题目是说有一个链表，里面可能有个圈。判断是否有圈以及若有，找圈的起点。
这题我假设读者都知道快慢指针解法。现在来讲一下快慢指针解法为什么work。
将链表部分看做一段带结的绳子，将圈部分看作一个带结的圈，将绳子绕在圈上，使得结点一一对应 (绳子可能更长，请自行想象)。
这样我们的快慢指针其实就有了两种位置，一种是圈上的位置，一种是实际链表上的位置 (0-8, 1-9, 2-10, 3-11…)。
快慢指针从同一点出发，它们在实际链表中相遇时，其圈位置必然和起点一样 (从0出发，最后必在8处相遇)。
这时候我们让慢指针继续走，并且在绳子开头再开始走一个慢指针，这俩指针的圈位置一直都是相同的，所以它们在实际链表中如果相遇，一定是圈和绳子的共有节点 (一个从0出发，一个从8出发，必在4处相遇)。
以上。
Read full article from 最后解释一遍快慢指针法解带圈链表问题 « Ashes of Time
No comments:
Post a Comment