Java 双链表，交换节点

Question

我在Java中实现双链表时遇到了问题。特别是交换 2 个以下节点（在我的情况下，节点包含一个政治候选人）。
假设以下 DLL
：头部-->1 -->2 --> 3 -->4 -->尾

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 = "Reversen";
    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

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

• N1 和 N2 是相邻节点
N1
• 在 N2 之前（ N1 --> N2 和 N1 <-- N2）。
• N1 和 N2 都不是头部或尾部元素（因为reverseTwoNode不会更新列表）

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

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

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

然后在：

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

N1.getNextNode()不是原始值。由于N1.setNextNode(N2.getNextNode())，这是N2.getNextNode().

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

Answer 2

删除 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);
    }
}