Java实现唯一元素有序链表：插入去重问题求助

我帮你捋捋这个问题哈～你现在的inserirOrdem方法只处理了按序插入的逻辑，但没做重复元素的校验，所以不管元素是否存在都会被添加。咱们来修改这个方法，同时实现按字母顺序插入和自动排除重复元素的需求：

首先先把你给出的代码片段贴出来：

public void inserirOrdem( String elemento ) { 
    No novoNo = new No( elemento ); 
    No actual = cabeca; //actual=head of the list 
    No anterior = null; 
    ...
}

问题核心 #

你的代码缺少了重复元素的判断逻辑，也没在遍历过程中同时兼顾“找插入位置”和“检查重复”这两个目标。我们需要在遍历链表时，一边对比元素的字母顺序，一边检查当前元素是否和要插入的元素完全一致。

修正后的完整方法 #

假设你的No节点类有getElemento()（获取节点存储的字符串）、getProximo()（获取下一个节点）、setProximo(No proximo)（设置下一个节点）这几个方法，修正后的代码如下：

public void inserirOrdem(String elemento) {
    // 处理空链表的特殊情况：直接把新节点设为表头
    if (cabeca == null) {
        cabeca = new No(elemento);
        return;
    }

    No novoNo = new No(elemento);
    No actual = cabeca;
    No anterior = null;

    while (actual != null) {
        // 用compareToIgnoreCase忽略大小写比较，如果你需要严格区分大小写就用compareTo
        int comparacaoResultado = elemento.compareToIgnoreCase(actual.getElemento());
        
        if (comparacaoResultado == 0) {
            // 元素已存在，直接返回，不执行插入
            System.out.println("元素 '" + elemento + "' 已存在，跳过插入");
            return;
        } else if (comparacaoResultado < 0) {
            // 找到了合适的插入位置（当前节点比新元素大），跳出循环准备插入
            break;
        }
        
        // 如果当前节点比新元素小，继续往后遍历
        anterior = actual;
        actual = actual.getProximo();
    }

    // 执行插入操作，分三种场景：插在表头、插在链表中间、插在表尾
    if (anterior == null) {
        // 插在表头
        novoNo.setProximo(cabeca);
        cabeca = novoNo;
    } else {
        // 插在anterior和actual之间（包括表尾，此时actual为null）
        novoNo.setProximo(actual);
        anterior.setProximo(novoNo);
    }
}

关键逻辑说明 #

1. 空链表处理：如果链表还没有任何节点，直接把新节点设为表头，避免后续遍历出现空指针。
2. 重复判断：在遍历过程中，一旦发现comparacaoResultado == 0，说明当前节点的元素和要插入的元素完全一致（忽略大小写的话），直接return终止方法，不插入重复元素。
3. 插入位置定位：通过compareToIgnoreCase的结果判断：
   • 结果小于0：新元素比当前节点元素小，应该插在当前节点前面，跳出循环准备插入。
   • 结果大于0：继续往后找合适的位置。
4. 插入操作：根据anterior是否为null，判断是插在表头还是链表中间/尾部。

注意事项 #

• 如果你需要严格区分大小写（比如"Apple"和"apple"算不同元素），把compareToIgnoreCase改成compareTo即可。
• 确保你的No类实现了对应的getter和setter方法，不然代码会报错。

内容的提问来源于stack exchange，提问作者Andreia F.