Java日记2018-05-03

第一题  链表中倒数第 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指向头结点移动,当再次相遇就是环入口

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容