题目描述：

 

 

 

 

 

 思路：

对上图示例 2，设置两个指针 A_ptr 和 B_ptr ，让A_ptr 初始 指向链表headA头部 (结点 0)， B_ptr初始指向链表headB头部(结点3),  

A_ptr 和 B_ptr同步地向后移动，A_ptr 到结点 0 所在链表尾部后，跳到headB头部(结点 3) 继续遍历,B_ptr到headB尾部后，

跳到headA头部继续遍历,对于示例 2，A_ptr  和 B_ptr一定会相遇在公共结点2上。

对于示例三，在A_ptr 和B_ptr 和都遍历完两个链表后，仍然没有相遇，返回 NULL。

代码如下：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
12     {
13         if(headA == NULL || headB == NULL)
14         {
15             return NULL;
16         }
17         ListNode *A_ptr = headA;
18         ListNode *B_ptr = headB;
19         int num_a = 0;
20         int num_b = 0;
21         while(num_a < 2 && num_b < 2)
22         {
23             if(A_ptr == NULL)//A_ptr 从headA遍历到尾部后，重新从headB开始遍历
24             {
25                 A_ptr = headB;
26                 ++num_a;
27             }
28             if(B_ptr == NULL)//B_ptr 从headB遍历到尾部后，重新从headA开始遍历
29             {
30                 B_ptr = headA;
31                 ++num_b;
32             }
33             if(A_ptr == B_ptr )//A_ptr和B_ptr相遇
34             {
35                 return A_ptr;
36             }
37             //两指针同步后移
38             A_ptr = A_ptr->next;
39             B_ptr = B_ptr->next;
40         }
41         //两指针都遍历完两个链表后，仍然没有相遇，说明两链表没有公共节点
42         return NULL;
43     }
44 };