Java双向链表元素交换（不修改数据/无集合）代码无限循环问题求助

我尝试在不修改节点数据、不使用集合类的情况下交换双向链表中的两个元素，编写了如下代码：

双向链表实现代码 #

package q2b;

public class DoublyLinkedList {
    static Node first;
    static Node last;
    
    public DoublyLinkedList() {
        first = null;
        last = null;
    }
    
    public void display() {
        Node current = first;

        if(first == null) {
            System.out.println("List is empty.");
        }
        System.out.print("Nodes: ");
        while(current != null) {
            System.out.print(current.data+", ");
            current = current.next;
        }
        System.out.println();
    }
    
    public void add(int x) {
        if (last==null) {
            Node temp = new Node(x);
            last = temp;
            first = temp;
        }
        
        else {
            Node temp = new Node(x);
            last.next = temp;
            temp.prev = last;
            last = temp;
        }
    }
    
    public Pair find(int x, int y) {
        Node n1 = null;
        Node n2 = null;
        Node temp = first;
        
        while (temp != null) {
            if (temp.data == x) {
                n1 = temp;
            }
            else if (temp.data == y) {
                n2 = temp;
            }
            temp = temp.next;
        }
        return new Pair(n1,n2);
    }
    
    public void swap(int x, int y) {
        if (first == null || first.next == null || x == y) {
            return;
        }
        
        Pair p = find(x,y);
        
        Node n1 = p.first;
        Node n2 = p.second;
        
        if (n1==first) {
            first = n2;
        }
        else if (n2 == first) {
            first = n1;
        }
        
        if (n1 == last) {
            last = n2;
        }
        else if (n2 == last) {
            last = n1;
        }
        
        Node temp;
        temp = n1.next;
        n1.next = n2.next;
        n2.next = temp;
        
        if (n1.next != null) {
            n1.next.prev = n1;
        }
        if (n2.next != null) {
            n2.prev.next = n2;
        }
        
        temp = n1.prev;
        n1.prev = n2.prev;
        n2.prev = temp;
        
        if (n1.prev != null) {
            n1.prev.next = n1;
        }
        if (n2.prev != null) {
            n2.prev.next = n2;
        }
    }
}

测试主类代码 #

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.add(2);
        list.add(4);
        list.add(6);
        list.add(8);
        list.add(10);
        list.display();
        list.swap(6, 8);
        list.display();
    }
}

运行代码时程序陷入无限循环直至崩溃，推测是swap函数存在问题，求排查思路。

排查思路与问题分析 #

1. find方法的逻辑缺陷 #

当前find方法使用else if判断节点值，这会导致：

• 如果链表中先出现y再出现x，n1无法被赋值（进入y的判断后会跳过x的判断）
• 如果存在重复值，会漏找目标节点

修正方案：将两个判断改为独立的if，确保所有匹配节点都能被找到：

public Pair find(int x, int y) {
    Node n1 = null;
    Node n2 = null;
    Node temp = first;
    
    while (temp != null) {
        if (temp.data == x) {
            n1 = temp;
        }
        if (temp.data == y) { // 去掉else，改为独立if
            n2 = temp;
        }
        temp = temp.next;
    }
    return new Pair(n1,n2);
}

2. swap方法的指针循环错误 #

这是导致无限循环的核心原因，以测试用例中交换6（n1）和8（n2）为例：

• 原链表结构：6.next = 8，8.prev = 6
• 交换next指针后：n1.next = 10，n2.next = 6
• 此时代码执行if (n2.next != null) {n2.prev.next = n2;}，n2.prev仍是6（n1），这段代码会把n1.next重新设为8（n2），形成n1.next = n2且n2.next = n1的循环链表，最终导致display方法无限遍历。

关键错误点：

• 错误地将n2.next.prev = n2写成n2.prev.next = n2，前者是修正n2后继节点的前驱指针，后者属于修改n2前驱节点的后继指针，应放在处理prev指针的逻辑中。
• 指针修改顺序混乱，相邻节点交换时会出现指针互相覆盖的问题。

修正后的swap方法：

public void swap(int x, int y) {
    if (first == null || first.next == null || x == y) {
        return;
    }

    Pair p = find(x, y);
    Node n1 = p.first;
    Node n2 = p.second;

    // 如果其中一个节点不存在，直接返回
    if (n1 == null || n2 == null) {
        return;
    }

    // 保存n1和n2的前后节点，避免修改时被覆盖
    Node n1Prev = n1.prev;
    Node n1Next = n1.next;
    Node n2Prev = n2.prev;
    Node n2Next = n2.next;

    // 处理头节点
    if (n1 == first) {
        first = n2;
    } else if (n2 == first) {
        first = n1;
    }

    // 处理尾节点
    if (n1 == last) {
        last = n2;
    } else if (n2 == last) {
        last = n1;
    }

    // 交换n1和n2的前驱指针
    n1.prev = n2Prev;
    n2.prev = n1Prev;

    // 交换n1和n2的后继指针
    n1.next = n2Next;
    n2.next = n1Next;

    // 更新n1前驱节点的后继指针
    if (n1.prev != null) {
        n1.prev.next = n1;
    }

    // 更新n1后继节点的前驱指针
    if (n1.next != null) {
        n1.next.prev = n1;
    }

    // 更新n2前驱节点的后继指针
    if (n2.prev != null) {
        n2.prev.next = n2;
    }

    // 更新n2后继节点的前驱指针
    if (n2.next != null) {
        n2.next.prev = n2;
    }
}

这个修正版本先保存所有需要的指针，再统一修改，避免了指针覆盖和循环问题，同时增加了节点不存在的判断逻辑，提升鲁棒性。

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