用于在不交换数据的情况下交换链表中的节点的 JavaScript 程序

什么是链表?

在计算机科学中，链表（linked list）是一种数据结构，用于储存有序的元素集合。每个元素包含两个字段：一个是存储元素本身的值（可能是任何类型），另一个是指向下一个元素的引用--即链。简单地说，链表就是一个由节点组成的线性集合，每个节点包含着数据和指向下一个节点的引用。

链表分为单向链表和双向链表两种，单向链表每个节点只有指向下一个节点的引用，双向链表则同时具有指向前一个节点和后一个节点的引用。

class Node {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}
class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

两个节点的交换

交换链表中的两个节点，我们可以先找到待交换节点的前驱节点，然后通过改变前驱节点的指向，实现两个节点的交换。

找到待交换节点的前驱节点

我们遍历链表找到待交换节点的前驱节点，若链表中存在重复元素，需要特殊处理。具体过程是，从头节点开始一直遍历到目标节点的前面一个节点，时间复杂度为O(n)。

function findPrevNode(head, node) {
    let prev = null;
    let curr = head;
    while (curr !== node) {
        prev = curr;
        curr = curr.next;
    }
    return prev;
}

交换节点并修改指针

找到待交换节点的前驱节点之后，我们可以通过修改指针实现两个节点的交换。具体步骤：

保存前驱节点 `prev`

交换 `prev` 的下一个节点和 `prev.next` 的下一个节点

将 `prev.next` 指向 `prev.next.next`

将 `prev.next.next` 的下一个节点指向 `prev.next`

返回新的头节点

function swapNodes(head, node1, node2) {
    if (!node1 || !node2) return head;
    // 保存前驱节点
    let prev1 = findPrevNode(head, node1);
    let prev2 = findPrevNode(head, node2);
    // 处理相邻节点的情况
    if (prev1 === node2) {
        [node1, node2] = [node2, node1];
        [prev1, prev2] = [prev2, prev1];
    }
    // 交换节点并修改指针
    let temp = node2.next;
    node2.next = node1.next;
    node1.next = temp;
    prev1.next = node2;
    prev2.next = node1;
    return prev1 === head ? node2 : head;
}

上面的代码实现了两个节点的交换，但并没有考虑这两个节点是否相邻，下面给出完整的代码实现：

class Node {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}
class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    addNode(val) {
        const node = new Node(val, null);
        if (!this.head) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        this.length++;
    }
    findPrevNode(node) {
        let prev = null;
        let curr = this.head;
        while (curr !== node) {
            prev = curr;
            curr = curr.next;
        }
        return prev;
    }
    swapNodes(node1, node2) {
        if (!node1 || !node2) return;
        // 保存前驱节点
        let prev1 = this.findPrevNode(node1);
        let prev2 = this.findPrevNode(node2);
        // 处理相邻节点的情况
        if (prev1 === node2) {
            [node1, node2] = [node2, node1];
            [prev1, prev2] = [prev2, prev1];
        }
        // 交换节点并修改指针
        let temp = node2.next;
        node2.next = node1.next;
        node1.next = temp;
        prev1.next = node2;
        prev2.next = node1;
        this.head = prev1 === this.head ? node2 : this.head;
    }
}

总结

链表是一种常见的数据结构，它的特点是可以动态地管理数据内存。但是由于链表节点的单向性，所以对其进行操作时往往需要引入前驱节点。在本文中，我们讨论了两个节点在链表中的交换，并通过代码实现了该功能。

双向链表相对于单向链表，其节点具有了两个指针，一个指向前驱节点，一个指向后继节点，因此在双向链表中节点的交换操作要比单向链表更加方便。但是双向链表的内存占用会比单向链表更大，因此要根据实际需要进行选择。