LeetCode 1721 交换链表中的节点

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var swapNodes = function(head, k) {
    let first = head;
    for (let i = 1; i < k; ++i) {
        first = first.next;
    }
    
    let second = head;
    let fast = first; // 快指针先站在正数第 k 个节点
    while (fast.next) {
        fast = fast.next;
        second = second.next;
    }
    
    // JS 无内置 swap 函数，需手动实现值交换
    const temp = first.val;
    first.val = second.val;
    second.val = temp;
    
    return head;
};

注意：JavaScript 中无内置 swap 函数，需手动实现值的交换。

解题思路

1. 定位正数第 k 个节点：从头节点出发，移动 k-1 步，直接找到目标节点。需注意循环次数，因为链表从 1 开始索引。
2. 定位倒数第 k 个节点：使用'前后指针（快慢指针）'实现。先让快指针走 k 步（即站在正数第 k 个节点），再让快慢指针同步走。当快指针到达末尾时，慢指针即为倒数第 k 个节点。此方法只需一次遍历，避免二次统计长度。
3. 交换值而非节点：仅交换两个节点的 val，不修改链表的 next 指针。这彻底避免了节点丢失的问题，是最简洁且安全的操作方式。

常见错误与注意事项

总结

1. 核心逻辑：先精准定位两个目标节点，仅交换值而非节点，避免链表结构修改带来的节点丢失问题。
2. 关键技巧：用间隔 k 的快慢指针一次遍历找到倒数第 k 个节点，时间复杂度 O(n)，空间复杂度 O(1)。
3. 细节注意：循环次数为 k-1 而非 k，快慢指针同步移动的终止条件是 fast->next == nullptr，这些细节保证了定位的准确性。