手帐 Blog

主题

13 · 链表进阶 ​

目标：会环检测、相交链表、合并两个有序链表；面试能画图讲清指针怎么走。

为什么面试会考 ​

这三道是链表「必考三联」：

  • 环：快慢指针会不会相遇
  • 相交：长度对齐或「走对方的路」
  • 合并：双指针归并，和合并有序数组同一思想

零基础概念 ​

题型核心一句话
有环？快指针一次两步、慢指针一次一步，相遇则有环
相交？走到头后跳到另一条头，路径长度最终对齐
合并谁小接谁，接完接剩余尾巴

JS 模板：快慢指针找环 ​

js
let slow = head
let fast = head
while (fast && fast.next) {
  slow = slow.next
  fast = fast.next.next
  if (slow === fast) return true // 有环
}

精讲题 ​

LeetCode 141. 环形链表 ​

js
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let slow = head
  let fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}

复杂度：时间 O(n)，空间 O(1)。（也可用 Set 记访问过的结点，空间 O(n)。）

LeetCode 160. 相交链表 ​

两指针分别从 headA、headB 走；走到 null 就换到对方的头。若相交，会在交点相遇；若不相交，会同时走到 null。

js
/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null
  let a = headA
  let b = headB
  while (a !== b) {
    a = a ? a.next : headB
    b = b ? b.next : headA
  }
  return a
}

直觉：a 走完 A 再走 B，b 走完 B 再走 A，总步数相同，相交点对齐。

LeetCode 21. 合并两个有序链表 ​

js
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  const dummy = new ListNode(0)
  let cur = dummy
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      cur.next = list1
      list1 = list1.next
    } else {
      cur.next = list2
      list2 = list2.next
    }
    cur = cur.next
  }
  cur.next = list1 || list2
  return dummy.next
}

练习清单 ​

题提示
LeetCode 142. 环形链表 II相遇后再让一指针从头走，再相遇即环入口
LeetCode 2. 两数相加模拟竖式加法，注意进位
LeetCode 24. 两两交换链表中的节点哨兵 + 三个指针改指向
LeetCode 148. 排序链表（可选）归并：找中点拆开再合并

今日验收 ​

  • [ ] 141 能不看稿写快慢指针
  • [ ] 160 能口述「换头走」为什么长度对齐
  • [ ] 21 会用哨兵合并，并接上剩余尾巴

若你以前见过 ​

「快慢指针」在数组去重里叫读写指针；在链表环检测里是同一节奏的不同舞台。