手帐 Blog

主题

12 · 链表基础 ​

目标：看懂 ListNode；会用哨兵节点；独立写出反转链表、按值删除节点。

为什么面试会考 ​

数组靠下标，链表靠「下一个指针」。前端偶发考链表，但一考就是：

  • 会不会画指针图（别在脑子里乱跳）
  • 会不会处理空链表、单节点、删头节点

会了反转与哨兵，进阶题（环、相交、合并）只是同一套指针功夫的变体。

零基础概念 ​

LeetCode 常见结点定义：

js
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val
  this.next = next === undefined ? null : next
}
说法含义
head第一个结点
null空（链表结束）
哨兵 / dummy假头结点，统一「删头」等边界

画图习惯：每改一次 next，在纸上改一次箭头。

JS 模板：哨兵 + 遍历 ​

js
function walk(head) {
  const dummy = new ListNode(0, head)
  let cur = dummy
  while (cur.next) {
    // 根据题意改 cur.next
    cur = cur.next
  }
  return dummy.next
}

精讲题 ​

LeetCode 206. 反转链表 ​

把 1 → 2 → 3 → null 变成 3 → 2 → 1 → null。

思路：三个指针 prev / cur / next，每次把 cur.next 指回 prev。

js
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prev = null
  let cur = head
  while (cur) {
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
}

复杂度：时间 O(n)，空间 O(1)。

递归写法（理解即可，面试先写迭代更稳）：

js
var reverseList = function (head) {
  if (!head || !head.next) return head
  const newHead = reverseList(head.next)
  head.next.next = head
  head.next = null
  return newHead
}

LeetCode 203. 移除链表元素 ​

删除所有 val === val 的结点。删头时用哨兵最省事。

js
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  const dummy = new ListNode(0, head)
  let cur = dummy
  while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next
    } else {
      cur = cur.next
    }
  }
  return dummy.next
}

LeetCode 19. 删除链表的倒数第 N 个结点（快慢指针预热） ​

让 fast 先走 n 步，再 fast/slow 一起走；fast 到末尾时，slow.next 就是待删结点。

js
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  const dummy = new ListNode(0, head)
  let fast = dummy
  let slow = dummy
  for (let i = 0; i < n; i++) fast = fast.next
  while (fast.next) {
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next
  return dummy.next
}

练习清单 ​

题提示
LeetCode 876. 链表的中间结点快慢指针：快两步、慢一步
LeetCode 83. 删除排序链表中的重复元素有序，相邻相同就跳过
LeetCode 237. 删除链表中的节点只给被删结点：把下一个的值拷过来再跳过下一个
LeetCode 234. 回文链表找中点 + 反转后半 + 比较（可后做）

今日验收 ​

  • [ ] 能手写 ListNode 与反转链表三指针
  • [ ] 解释哨兵为什么能简化「删头」
  • [ ] 19 能说清「fast 先走 n 步」

若你以前见过 ​

C++ 里常见 ListNode*；JS 里没有指针类型，但「引用指向对象」的心智一样——改 next 就是改箭头。