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.

 

Notes:

• • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

思路：假设A与B长度相等，则从链表头开始一一对比即可。

假设A与B长度不等，则进行一一对比时，短的链表会先被遍历完。这时，让该指针指向另一个链表的表头，继续进行。当长链表也被遍历完时，则其指针指向短的链表。通过这种方式，一定可以找到回合点，因为两个指针遍历的总长度是相等的，都是长链表和短链表各走了一遍。

 

1 class Solution { 2 public: 3     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 4         ListNode *ha = headA; 5         ListNode *hb = headB; 6         if (ha == NULL || hb == NULL) return NULL; 7         while (ha != NULL && hb != NULL && ha != hb) 8         { 9             ha = ha->next;10             hb = hb->next;11             if (ha == hb) return ha;12             if (ha == NULL) ha = headB;13             if (hb == NULL) hb = headA;14         }15         return ha;16     }17 };