Java双向链表交换相邻节点重复问题排查与修复

问题场景 #

双向链表练习中，非相邻节点交换功能正常，但相邻节点交换时出现异常：

• 初始链表：1.Carrot、2.Candy、3.Watermelon、4.Bread
• 交换位置2和3后，结果变为：1.Carrot、2.Watermelon、3.Watermelon、4.Bread

尝试过临时节点保存原prev/next、判断prev/next是否相等的方法，均未解决问题。

代码问题分析 #

现有switchSpace方法的核心问题：

1. 错误创建新节点：双向链表交换节点无需新建节点，创建新节点会打乱原链表的引用关系，尤其相邻节点场景下，会导致指针修改时互相干扰，最终出现重复节点。
2. 未处理相邻节点特殊逻辑：相邻节点的prev/next存在依赖关系，直接复用非相邻的指针修改逻辑会导致引用覆盖。

修正方案 #

直接操作原节点的prev/next指针，分三种场景处理：两节点相同、两节点相邻、两节点不相邻，同时处理头/尾节点的边界情况。

修正后的代码 #

public void switchNodes(int firstSpace, int secondSpace){
    if(isEmpty()|| firstSpace < 0 || secondSpace < 0){
        System.out.println("List is empty or one of spaces entered does not have anything in it.");
        return;
    }
    
    Node<E> firstN = current(firstSpace);
    Node<E> secondN = current(secondSpace);
    
    switchSpace(firstN, secondN);
}

/**
 * 交换双向链表中两个节点的位置
 */
private void switchSpace(Node<E> firstSwitch, Node<E> secondSwitch) {
    // 两个节点为同一节点，无需交换
    if (firstSwitch == secondSwitch) {
        return;
    }

    // 保存原始前驱和后继节点
    Node<E> firstPrev = firstSwitch.getPrev();
    Node<E> firstNext = firstSwitch.getNext();
    Node<E> secondPrev = secondSwitch.getPrev();
    Node<E> secondNext = secondSwitch.getNext();

    // 场景1：firstSwitch在secondSwitch的前一位（相邻）
    if (firstNext == secondSwitch) {
        firstSwitch.setPrev(secondSwitch);
        firstSwitch.setNext(secondNext);
        
        secondSwitch.setPrev(firstPrev);
        secondSwitch.setNext(firstSwitch);
        
        // 更新外部节点引用
        if (firstPrev != null) {
            firstPrev.setNext(secondSwitch);
        }
        if (secondNext != null) {
            secondNext.setPrev(firstSwitch);
        }
    } 
    // 场景2：secondSwitch在firstSwitch的前一位（相邻）
    else if (secondNext == firstSwitch) {
        switchSpace(secondSwitch, firstSwitch);
    } 
    // 场景3：两节点不相邻
    else {
        firstSwitch.setPrev(secondPrev);
        firstSwitch.setNext(secondNext);
        
        secondSwitch.setPrev(firstPrev);
        secondSwitch.setNext(firstNext);
        
        // 更新外部节点引用
        if (firstPrev != null) {
            firstPrev.setNext(secondSwitch);
        }
        if (firstNext != null) {
            firstNext.setPrev(secondSwitch);
        }
        if (secondPrev != null) {
            secondPrev.setNext(firstSwitch);
        }
        if (secondNext != null) {
            secondNext.setPrev(firstSwitch);
        }
    }
}

关键修正点 #

• 移除创建新节点的逻辑，直接操作原节点指针，避免引用混乱。
• 增加节点同一性判断，跳过无意义操作。
• 分场景处理相邻/非相邻节点，覆盖所有交换情况。
• 处理头/尾节点的null指针边界，避免运行时异常。

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