如何将双向链表中的节点与其前一个节点交换

Question

我有一个项目，我必须做的一件事是将作为参数给定的节点与它之前的方法交换。如果它是第一个，那也没关系，但我和我的室友一整天都在尝试这个。我们尝试制作多个临时节点并弄乱它们，并尝试仅交换节点的元素。很难确切地说出我们做错了什么。我觉得这应该比我们想象的要简单得多，但我们花了很多时间来做这件事。任何建议或帮助将不胜感激。

Answer 1

这听起来像是一个 class 问题。

每个节点都有一个指向前一个节点和一个指向下一个节点的指针，对吧？ head 没有 "previous" 指针（例如它为空或有一些特殊值）。

要交换节点，您从：

开始

Node node = the node passed in
Node previousNode = node.previous

除了 previousNode 为空的特殊情况：

previousNode.next = node.next;         // this used to point to node
previousNode.previous.next = node;     // this used to point to previousNode
node.previous = previousNode.previous; // this used to point to previousNode
node.next.previous = previousNode;     // this used to point to node
node.next = previousNode;
previousNode.previous = node;

Answer 2

之前:

pp -> p -> node -> n

之后：

pp -> node -> p -> n

所以你需要更新：

1. pp.next
2. node.previous
3. node.next
4. p.previous
5. p.next
6. n.previous

因此：

private void swapWithPrevious(Node node) {
   if(n.previous == null) { // first node
       return;
   }

   Node p = node.previous;
   Node pp = p.previous;
   Node n = node.next;
   if(pp != null) {
       pp.next = node;
   }
   node.previous = pp;
   node.next = p;
   p.previous = node;
   p.next = n;
   if(n != null) {
       n.previous = p;
   }
}