JavaScript 简单链表题目试析-EW帮帮网

JavaScript 简单链表题目试析

147. 对链表进行插入排序

算法思路

插入排序在链表中的实现其实比在数组中更自然，因为链表本身的结构让节点插入变得很高效——只需要调整指针，而不需要像数组那样移动大量元素。

我们依然是将链表分成已排序和未排序两部分。开始时已排序部分只有第一个节点，然后逐个处理未排序部分的节点，找到它们在已排序部分的正确位置并插入。

为了处理可能在头部插入的情况，使用一个虚拟头节点可以大大简化代码逻辑。

JavaScript 实现

function insertionSortList(head) {
    if (!head) return null;
    
    // 创建虚拟头节点
    const dummyHead = new ListNode(0);
    dummyHead.next = head;
    
    let lastSorted = head;     // 已排序部分的最后一个节点
    let curr = head.next;      // 当前待插入的节点
    
    while (curr !== null) {
        if (lastSorted.val <= curr.val) {
            // 当前节点大于等于已排序部分的最后一个节点，位置正确
            lastSorted = lastSorted.next;
        } else {
            // 需要找到插入位置
            let prev = dummyHead;
            while (prev.next.val <= curr.val) {
                prev = prev.next;
            }
            // 执行插入操作
            lastSorted.next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
        }
        curr = lastSorted.next;
    }
    
    return dummyHead.next;
}

1721. 交换链表中的节点

算法思路

这个问题的关键在于如何高效地找到正数第 k 个和倒数第 k 个节点。使用双指针技巧可以在一次遍历中完成这个任务。

先用一个指针移动 k-1 步找到正数第 k 个节点，然后同时移动两个指针，当第一个指针到达末尾时，第二个指针正好指向倒数第 k 个节点。

JavaScript 实现

function swapNodes(head, k) {
    let fast = head;
    let firstNode = null;
    let secondNode = head;
    
    // 找到正数第 k 个节点
    for (let i = 1; i < k; i++) {
        fast = fast.next;
    }
    firstNode = fast;
    
    // 找到倒数第 k 个节点
    while (fast.next !== null) {
        fast = fast.next;
        secondNode = secondNode.next;
    }
    
    // 交换节点值
    [firstNode.val, secondNode.val] = [secondNode.val, firstNode.val];
    
    return head;
}

JavaScript 与 C 语言的差异体验

从 C 语言转到 JavaScript 来处理链表问题，有几个明显的不同点值得注意。

内存管理变得简单了 在 C 中我们需要小心翼翼地处理 malloc 和 free，生怕出现内存泄漏。但在 JavaScript 中，垃圾回收机制自动处理这些琐事，让我们可以更专注于算法逻辑本身。不过这也意味着我们对内存的控制力变弱了，有时候可能不太习惯。

语法更加简洁 JavaScript 的解构赋值特性让变量交换变得异常简单，一行 [a, b] = [b, a] 就搞定了在 C 中需要三行代码才能完成的任务。这种语法糖确实让代码更加清晰易读。

类型系统更加灵活 不需要在变量声明时指定类型，这让代码写起来更快，但也增加了运行时出现类型错误的风险。

空值表示不同 从 NULL 到 null 的转变虽然只是大小写的区别，但在实际编程中经常需要提醒自己不要写错。JavaScript 的 null 和 undefined 之间的细微差别也是初学者容易困惑的地方。

在实际开发中，虽然现代 JavaScript 提供了很多高级特性，但对于链表这种基础数据结构，保持代码的清晰和简洁往往比使用炫技式的复杂写法更重要。

JavaScript 简单链表题目试析