基于递归的链表升序判断:元素比较逻辑异常如何修正
代码核心问题定位
原实现的三个逻辑偏差直接导致所有长度超过2的链表判断结果不符合预期,和你遇到的异常表现完全对应:
- 相邻节点比较后提前返回:只要当前节点与下一节点满足升序关系,就直接返回
true,完全跳过后续节点的校验流程,直接导致含逆序对的长链表被误判为合法升序(对应100、200、100的非升序链表错误返回true的现象) - 递归结果未逐层传递:调用
this.next.ascending()时没有将递归返回的结果作为当前方法的返回值,即便后续节点存在逆序对,校验结果也会被直接丢弃 - 递归终止条件反向:当遍历到链表尾节点(
this.next == null)时,代表前置所有相邻节点对都已通过升序校验,此时应该返回true,但原代码在该分支下直接走到方法末尾返回false,导致合法升序的长链表被误判为非升序(对应100、200、300的合法升序链表错误返回false的现象)
修正后的实现
修正后Cells类的ascending方法遵循递归校验的标准流程:
- 先处理递归终止场景:走到链表尾节点时直接返回
true - 遇到相邻逆序对时直接提前返回
false,无需继续递归 - 相邻对满足升序要求时,直接返回下一节点的递归校验结果,让结果逐层向上传递
修正后的代码:
public boolean ascending() { // 遍历到尾节点,说明所有前置相邻对都符合升序要求 if (this.next == null) { return true; } // 当前相邻对不满足升序,直接返回false if (this.employee.getNumbers() >= this.next.employee.getNumbers()) { return false; } // 递归校验后续相邻对,将结果逐层返回 return this.next.ascending(); }
外层链表类的
ascending方法逻辑无需调整,空链表返回false的判定符合需求;修正后单节点链表会返回true,也符合升序的通用定义(无相邻逆序对)。
内容的提问来源于stack exchange,提问作者Evelyne
相关产品推荐
相关产品推荐

