/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur_headA=headA;
ListNode *cur_headB=headB;
int num_headA=;
int num_headB=; while(cur_headA!=NULL)//统计headA个数
{
num_headA++;
cur_headA=cur_headA->next;
}
while(cur_headB!=NULL)//统计headB个数
{
num_headB++;
cur_headB=cur_headB->next;
} if(num_headA*num_headB==)//如果有一个为NULL，返回NULL
return NULL; if(num_headA>num_headB)//不妨设headA的个数大于headB
{
cur_headA=headA;
cur_headB=headB;
}
else
{
cur_headA=headB;
cur_headB=headA;
} int temp=abs(num_headA-num_headB);//让headA的指针先走到和headB的开头相同的位置
while(temp>)
{
cur_headA=cur_headA->next;
temp--;
} if(cur_headA==cur_headB)//如果已经相同，直接返回
return cur_headA; while(cur_headA->next!=cur_headB->next)//一直往后走，最差也就走到头NULL
{
cur_headA=cur_headA->next;
cur_headB=cur_headB->next;
}
return cur_headA->next; }
};
分析：
在剑指offer上见过，除了上述方法，还有就是使用栈，先分别压入栈，再通过两个栈从尾向头弹出比较，只不过空间复杂度是O(n)。
刚才chorm崩了，所以这是第二遍。。。