• 题目
• 大致意思
• 解决方案
• 源代码

题目

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.

大致意思

给出两个链表，找到他们相加的点，如果没有的话，就返回null

解决方案

• 我们让两条链表分别从各自的开头开始往后遍历，当其中一条遍历到末尾时，我们跳到另一个条链表的开头继续遍历。
• 两个指针最终会相等
  • 一种情况是在交点处相遇
  • 另一种情况是在各自的末尾的空节点处相等。
  • 为什么一定会相等呢，因为两个指针走过的路程相同，是两个链表的长度之和，所以一定会相等。

源代码

var getIntersectionNode = function(headA, headB) {
  var a = headA;
  var b = headB;
  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
  return a;
};