题目:给定一个非空单向无环链表,获取链表的中间结点。注意,如果链表的节点个数为偶数,即其中间部分为两个节点,算法需要返回后一个节点。本篇经验将分享如何通过双指针算法进行求解。
工具/原料
1
Eclipse
2
JDK1.8
方法/步骤
1
声明一个静态内部类,表示链表节点,通过该类对象可以构建一条单向的链表结构。
2
实现快慢指针算法,算法思想:1. 声明快慢两个指针节点,初始均指向链表头节点。2. 快指针每次移动两步,慢指针每次移动一步,直到快指针不满足移动条件。3. 此时慢指针即指向中间节点。
3
编写一个函数,将链表结构转变为字符串,用于辅助本地测试。
4
编写本地测试方法。
5
运行测试方法,观察控制台输出,符合预期,本地测试通过。
6
平台提交算法,测试通过。
注意事项
1
链表为非空单向无环链表。
2
如果链表节点个数为偶数,则返回中间两个节点的后一个节点。