You need to enable JavaScript to run this app. Java双向链表结构下迭代实现获取序列末尾Wagon节点的方法
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.20 06:45:03