原地交换双链表节点内存位置并保持链表遍历顺序的实现

我正在开发一个基于固定内存块分配的双链表程序，内存块初始化代码如下：

constexpr std::size_t numNodes = 15;
Node* block = new Node[numNodes];

我需要实现一个swap(Node* block, std::size_t i, std::size_t j)函数，交换内存块中索引i和j位置的节点内容，但必须保证双链表的遍历逻辑顺序完全不变。举个例子：

交换索引1和3之前：
链表: [A] -> [B] -> [C] -> [D]
内存: 10, 20, 30, 40（对应A、B、C、D的存储值）

交换索引1和3之后：
链表: [A] -> [B] -> [C] -> [D]
内存: 10, 40, 30, 20（B和D的内存位置互换，但链表顺序不变）

我自己写了一个初始版本，但无法覆盖所有边界情况——比如当两个节点在链表中相邻（即block[i]是block[j]的前驱/后继，而非内存索引相邻）时，函数会失效。初始实现代码如下：

void swap(Node* array, int i, int j) {
  if (i == j)
    return;

  // Swap the nodes
  Node temp = array[i];
  array[i] = array[j];
  array[j] = temp;

  // Update next and prev pointers for array[i]
  if (array[i].next) {
    array[i].next->prev = &array[i];
  }
  if (array[i].prev) {
    array[i].prev->next = &array[i];
  }

  // Update next and prev pointers for array[j]
  if (array[j].next) {
    array[j].next->prev = &array[j];
  }
  if (array[j].prev) {
    array[j].prev->next = &array[j];
  }
}

问题分析 #

初始实现的核心问题是：当两个节点在链表中相邻时，交换内存内容后，节点自身的prev/next指针仍指向对方原来的内存位置，仅更新相邻节点的指针会导致链表出现循环或断裂，无法维持原有逻辑顺序。

正确实现方案 #

首先假设Node结构体定义如下（可根据实际需求调整数据域）：

struct Node {
    int value; // 示例数据域
    Node* prev;
    Node* next;
};

以下是能覆盖所有边界情况的swap函数：

#include <algorithm> // 用于std::swap

void swap(Node* block, std::size_t i, std::size_t j) {
    if (i == j) return;

    Node* nodeI = &block[i];
    Node* nodeJ = &block[j];

    // 情况1：nodeI是nodeJ的直接前驱（链表中相邻）
    if (nodeI->next == nodeJ) {
        Node* prevI = nodeI->prev;
        Node* nextJ = nodeJ->next;

        // 交换内存中的节点内容
        std::swap(block[i], block[j]);
        Node* newNodeI = &block[i]; // 原nodeJ
        Node* newNodeJ = &block[j]; // 原nodeI

        // 更新前驱节点的指向
        if (prevI) {
            prevI->next = newNodeI;
        }
        newNodeI->prev = prevI;

        // 维护两个交换节点的相邻关系
        newNodeI->next = newNodeJ;
        newNodeJ->prev = newNodeI;

        // 更新后继节点的指向
        if (nextJ) {
            nextJ->prev = newNodeJ;
        }
        newNodeJ->next = nextJ;
        return;
    }

    // 情况2：nodeJ是nodeI的直接前驱（链表中相邻），复用情况1的逻辑
    if (nodeJ->next == nodeI) {
        swap(block, j, i);
        return;
    }

    // 情况3：两个节点在链表中不相邻
    Node* prevI = nodeI->prev;
    Node* nextI = nodeI->next;
    Node* prevJ = nodeJ->prev;
    Node* nextJ = nodeJ->next;

    // 交换内存中的节点内容
    std::swap(block[i], block[j]);
    Node* newNodeI = &block[i]; // 原nodeJ
    Node* newNodeJ = &block[j]; // 原nodeI

    // 把原nodeI的链表关系迁移到newNodeJ（原nodeI现在在j位置）
    if (prevI) {
        prevI->next = newNodeJ;
    }
    newNodeJ->prev = prevI;
    if (nextI) {
        nextI->prev = newNodeJ;
    }
    newNodeJ->next = nextI;

    // 把原nodeJ的链表关系迁移到newNodeI（原nodeJ现在在i位置）
    if (prevJ) {
        prevJ->next = newNodeI;
    }
    newNodeI->prev = prevJ;
    if (nextJ) {
        nextJ->prev = newNodeI;
    }
    newNodeI->next = nextJ;
}

实现说明 #

1. 提前返回无意义操作：当i和j相等时直接返回，避免无效处理。
2. 优先处理相邻节点：链表中相邻的节点交换后指针依赖关系复杂，单独处理可避免循环或断裂：
   • 若nodeI是nodeJ的前驱，交换后重新构建前驱、交换节点、后继之间的指针链。
   • 若nodeJ是nodeI的前驱，直接递归调用自身并交换i/j参数，复用已有逻辑。
3. 非相邻节点处理：先保存两个节点原来的前驱和后继，交换内存内容后，将原节点的链表关系分别迁移到新的内存位置，确保所有指向这两个节点的指针都更新到正确的地址。

内容的提问来源于stack exchange，提问作者Jonathon Halim