相交链表-简单

难度：简单

题目描述：
编写一个程序，找到两个单链表相交的起始节点。

解题思路：
两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。

var getIntersectionNode = function (headA, headB) {
  while (headA) {
    headA.flag = true;
    headA = headA.next;
  }
  while (headB) {
    if (headB.flag) return headB;
    headB = headB.next;
  }
  return null;
};

1
2
3
4
5
6
7
8
9
10
11

双指针
同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），如上图，设 A 为长链表
那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null

var getIntersectionNode = function (headA, headB) {
  // 清除高度差
  let pA = headA,
    pB = headB;
  while (pA || pB) {
    if (pA === pB) return pA;
    pA = pA === null ? headB : pA.next;
    pB = pB === null ? headA : pB.next;
  }
  return null;
};

1
2
3
4
5
6
7
8
9
10
11

← 旋转链表-中等环形链表 II-中等 →

# 相交链表-简单

相交链表-简单