第一题 链表中倒数第 K 个结点
解题思路:
设链表的长度为 N。设两个指针 P1 和 P2,先让 P1 移动 K 个节点,则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动,可以知道当 P1 移动到链表结尾时,P2 移动到 N - K 个节点处,该位置就是倒数第 K 个节点。
设链表的长度为 N。设两个指针 P1 和 P2,先让 P1 移动 K 个节点,则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动,可以知道当 P1 移动到链表结尾时,P2 移动到 N - K 个节点处,该位置就是倒数第 K 个节点。
第二题 链表中环的入口结点
使用双指针,一个指针 fast 每次移动两个节点,一个指针 slow 每次移动一个节点,假设到环入口距离x,当相遇时fast移动x+m*n,m是圈数,n是环长度,slow移动x+k,k是环内移动数。又因为fast=2*slow,那么x+k=m*n.代表x+k等于在环内走m圈,于是让fast指向头结点移动,当再次相遇就是环入口