链表公共节点

问题

给定两个单链表，找出它们的第一个公共节点。如果没有公共节点，返回 null。

链表A: 1 -> 2 -> 3
                  ↘
                    6 -> 7
                  ↗
链表B:      4 -> 5

上例中，第一个公共节点是 6。

解答

链表节点定义

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

方法一：哈希表

function getIntersectionNode(headA, headB) {
  // 用 Set 存储链表 A 的所有节点
  const visited = new Set();
  
  let curr = headA;
  while (curr) {
    visited.add(curr);
    curr = curr.next;
  }
  
  // 遍历链表 B，找第一个在 Set 中的节点
  curr = headB;
  while (curr) {
    if (visited.has(curr)) {
      return curr;
    }
    curr = curr.next;
  }
  
  return null;
}

时间复杂度 O(m + n)，空间复杂度 O(m)。

方法二：双指针（推荐）

function getIntersectionNode(headA, headB) {
  if (!headA || !headB) return null;
  
  let pA = headA;
  let pB = headB;
  
  // 两指针走过的总路程相同时会相遇
  // pA: A独有部分 + 公共部分 + B独有部分
  // pB: B独有部分 + 公共部分 + A独有部分
  while (pA !== pB) {
    pA = pA ? pA.next : headB;
    pB = pB ? pB.next : headA;
  }
  
  return pA;
}

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

测试代码

// 构建测试链表
//     1 -> 2
//            ↘
//              3 -> 4
//            ↗
//         5

const common = new ListNode(3);
common.next = new ListNode(4);

const headA = new ListNode(1);
headA.next = new ListNode(2);
headA.next.next = common;

const headB = new ListNode(5);
headB.next = common;

const result = getIntersectionNode(headA, headB);
console.log(result.val); // 3

关键点

• 公共节点指的是同一个节点引用，不是值相等
• 双指针法原理：两指针各走一遍两个链表，路程相等，必在公共节点相遇
• 若无公共节点，双指针最终都为 null，循环自然结束
• 哈希表法更直观，双指针法空间更优