循环链表indexOf方法未找到元素返回-1的实现问题咨询

问题根本原因 #

• 循环链表的结构特性为尾节点的next指向头节点，整个链表不存在next为null的节点，你原代码中的循环终止条件while(temp != null)永远成立，查找不存在的元素时会无限遍历整个链表，导致死循环。
• 你后续补充的while(temp == null)逻辑无任何作用，循环链表遍历过程中temp永远不会为null，这段代码不可能被触发。
• 原代码末尾返回index -1的逻辑错误，未匹配到元素时不需要通过变量计算，可直接返回-1。

修复代码 #

你只需要修改循环终止条件，判断是否遍历回到了起始的头节点即可，修改后的代码如下：

public int indexOf(int value){
    Node head = tail.next;
    Node temp = head;
    int count = 0;
    // 循环终止条件：再次遍历到头部节点，说明所有节点都已经检查过
    do {
        if(temp.value == value) {
            return count;
        }
        count++;
        temp = temp.next;
    } while(temp != head);
    // 遍历完所有节点仍未找到，直接返回-1
    return -1;
}

修复说明 #

• 首先把起始的头节点tail.next存下来，作为遍历结束的标记
• 使用do-while循环是为了先检查第一个头节点的元素，再判断是否要继续遍历，避免头节点就是目标元素的场景被跳过
• 当temp再次等于头节点时，说明已经绕完整个链表，没有找到目标元素，直接返回-1即可

内容的提问来源于stack exchange，提问作者Brittney P