链表题型汇总

  • 判断链表是否存在环，并找出这个环节点

通过快慢指针，如果快慢指针相遇，说明链表是存在环的。

剑指 Offer II 022. 链表中环的入口节点

方法1：遍历单链表，记录路径

方法2：不需要额外空间，通过以下方法

image-20221017112740803

fast比slow多走了k步，k是环长度的整数倍。

假设相遇点距离环的入口起点为m;则head距离环入口起点k-m【相遇点再走k-m步也能到达环的入口起点】