Java；在没有集合的情况下交换 DoublyLinkedList 中的两个元素而不更改数据

Question

好的，所以我正在尝试交换双向链表中的两个元素，而不更改数据且不使用集合。这是我到目前为止所拥有的；

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();
    }
}

现在当我去运行代码时，它只是无限运行直到崩溃。我假设我在交换函数中遗漏了一些东西，这使它陷入了死亡漩涡，但我不确定它是什么。谁能给我一些见解？

Answer 1

您的问题在：

if (n2.next != null) {
   n2.prev.next = n2;
}

这是因为

n1

和

n2

本来就是连续的节点，也就是说

prev

的

n2

是

n1

。因此，在交换了

next

和

n1

的

n2

之后，表达式

n2.prev.next = n2

等于

n1.next = n2

，它覆盖了

n1.next = n2.next

你之前做了几行并指向

n1

的

next 

回到

n2

而

n2

的下一个是

n1

，所以现在你有一个圆圈，其中

n1.next

指向

n2

和

n2.next

指向

n1

- 当你尝试遍历

display()

中的节点，这就是您的代码永远不会返回的原因。 一种可能的解决方案是将 if 更改为：

if (n2.next != null && n2.prev != n1) {
   n2.prev.next = n2;
}

我认为你必须对其他三个如果应用类似的处理