LINKED LIST

链表

160. 相交链表

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

例如，下面的两个链表：

  A:          a1 → a2
                     ↘
                       c1 → c2 → c3
                     ↗            
  B:     b1 → b2 → b3

在节点 c1 开始相交。

注意：

如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
    if(headA == null || headB == null)
        return null;

    ListNode a = headA, b = headB;

    while(a != b)
    {
        a = a == null ? headB : a.next;
        b = b == null ? headA : b.next;
    }
    return a;
}

原理很简单，len(A + B) = len(B + A)，所以A链表接在B链表后面为链表1，B链表接在A链表后面为链表2，链表1和链表2的长度相同，同时开始遍历，定能找到相同的节点(如果不存在则循环停止在a == b == null)。（如果不理解的话就按上面的例子画一下试试）