Java双链表，交换节点

Question

我在Java中实现一个双链接列表时遇到了一个问题。特别是要交换2个以下节点（在我的例子中，一个节点包含一个政治候选人）。
假设下面的DLL：
head-

public static void reverseTwoNode(Node<Candidate> N1, Node<Candidate> N2){
     N1.setNextNode(N2.getNextNode()); 
        N2.setPreviousNode(N1.getPreviousNode());

        if (N1.getNextNode() != null)
            N1.getNextNode().setPreviousNode(N1);

        if (N2.getPreviousNode() != null)
            N2.getPreviousNode().setNextNode(N2);


        N2.setNextNode(N1); 
        N1.setPreviousNode(N2);
}

作为输出，我没有从头到尾的正确DLL，但从头到尾都很好：

List of candidate 
head-->Jacques-->Joseph-->Francis-->Gilbert-->tail
Reverse
tail-->Gilbert-->Francis-->Joseph-->Jacques-->head

Reverse nodes : Francis , Joseph
List of candidate 
head-->Jacques-->Joseph-->Gilbert-->tail
Reverse
tail-->Gilbert-->Joseph-->Francis-->Jacques-->head

我已经写了几个版本的这个方法reverseTwoNode。我甚至尝试在节点内部交换数据，而不是交换节点，我也有同样的问题。你能帮我真是太好了，我花了这么多时间在这个简单的功能上，我看不出有什么干扰。。。提前谢谢，

也许这是显示方法的结果？？

 /* Display DLL from head to tail
 * @see java.lang.Object#toString()
 * @return str
 */
public String toString(){
    String str = "List of candidate \n";
    str += "head-->";

    Node<Candidate> iterator = this.getHead();

    while (iterator != null) {
        str += iterator.getCandidate().getName();
        str += "-->";
        iterator = iterator.getNextNode();
        }
    return str + "tail";    
}


/**
 * Return string that display DLL from tail to head
 * @return str
 */
public String reverseToString(){
    String str = "Reverse\n";
    str += "tail-->";

    Node<Candidate> iterator = this.getTail();

    while (iterator != null) {
        str += iterator.getCandidate().getName();
        str += "-->" ;
        iterator = iterator.getPreviousNode();
        }

    return (str + "head");
}

解决方案：我的方法addNode是假的，这里是一个正确的方法，在尾部添加一个节点：

public void addNode(Node<Candidate> C){
    if(tail == null){
        this.head = C;
        this.tail = C;
    }
    else{
        this.tail.setNextNode(C);
        this.tail.getNextNode().setPreviousNode(this.tail);
        this.tail = this.tail.getNextNode();
        this.tail.setNextNode(null);
    }   
    this.size ++;
}

Answer 1

删除if语句，因为它们会阻止您移动头部和尾部节点（当一个节点实际指向null时，可能会导致奇怪的问题）。我还假设您希望交换两个节点，而不管它们的位置如何（不必是两个相邻的节点）。

这应该只是交换节点，并保持列表的其余部分不变。

public static void reverseTwoNode(Node<Candidate> N1, Node<Candidate> N2){
    Node<Candidate> prevNode1 = N1.getPreviousNode();
    Node<Candidate> nextNode1 = N1.getNextNode();
    Node<Candidate> prevNode2 = N2.getPreviousNode();
    Node<Candidate> nextNode2 = N2.getNextNode();

    if(N2.getPreviousNode().equals(N1)) { // test for adjacent nodes
        N2.setPreviousNode(prevNode1);
        N2.setNextNode(N1);
        N1.setNextNode(nextNode2);
        N1.setPrevNode(N2);
    } else {
        N1.setPreviousNode(prevNode2);
        N1.setNextNode(nextNode2);
        N2.setPreviousNode(prevNode1);
        N2.setNextNode(nextNode1);
    }
}

Answer 2

如果满足以下假设，则发布的代码有效：

• N1和N2是相邻节点

检查一下：http://ideone.com/3AKsBx

对于更通用的解决方案，您需要一些辅助变量来存储N1/N2的下一个和前一个引用。因为当您这样做时：

N1.setNextNode(N2.getNextNode()); 
N2.setPreviousNode(N1.getPreviousNode());

然后在：

if (N1.getNextNode() != null)
    N1.getNextNode().setPreviousNode(N1);

N1。getNextNode（）不是原始值。这是N2。getNextNode（）由于N1。setNextNode（N2.getNextNode（））。

下面是一个例子：http://ideone.com/voaaTO