Java双向链表结构下迭代实现获取序列末尾Wagon节点的方法
双向链表Wagon类
getLastWagonAttached方法的非递归实现 核心遍历逻辑思路
你已搭建的“无后继返回自身、有后继向后移动”的分支逻辑方向完全正确,缺失的核心部分是把单次移动的判断改为持续迭代的循环,实现路径完全贴合双向链表的连接规则,不会破坏链表不变量:
- 定义独立的临时遍历游标,初始值绑定为当前调用方法的
this节点,全程不修改当前节点本身的指针属性,从根源上避免破坏原有链表结构 - 以“游标不存在后继节点”作为循环终止条件,只要游标满足存在后继的判断结果,就持续将游标移动到其指向的后继节点
- 循环终止时,游标指向的就是当前Wagon所属挂载序列的末尾节点,直接返回该游标值即可
这个逻辑天然兼容你已写好的基础分支:如果当前Wagon本身没有后续挂载车厢,循环第一次判断就会触发终止,返回初始的当前节点,完全符合功能预期。
参考实现代码
public Wagon getLastWagonAttached() { // 初始化遍历游标,不改动当前节点本身 Wagon traverseCursor = this; // 只要当前游标存在后继,就持续向后移动 while (traverseCursor.hasNextWagon()) { traverseCursor = traverseCursor.getNextWagon(); } // 无后继的节点即为序列末尾 return traverseCursor; }
实现注意事项
- 遍历全程仅顺着后继指针向后移动,不要误用双向链表的前驱指针反向遍历,否则会偏离“查找当前Wagon后续挂载序列末尾”的需求
- 不需要引入栈、队列等额外存储结构记录遍历路径,单靠临时游标即可完成全部逻辑,满足非递归迭代的性能要求,时间复杂度为O(n)、空间复杂度为O(1)
- 不要直接对
this节点的指针做重新赋值,否则会破坏当前节点在链表中的原有位置,甚至触发双向链表连接的一致性校验异常
内容的提问来源于stack exchange,提问作者Ronny Giezen
相关产品推荐
相关产品推荐

