题目描述

输入两个链表，找出它们的第一个公共结点。

 

思路：

题目说的很笼统，应该是有2个链表，找出公共点，第一个公共点后面的链表是共同所有的。可以用map做，直接检测map里有没有出现这个节点。

思路2：

统计2个链表的长度，i，j，长的链表先走|i-j|步，再一起走，如果有公共点，他们必然有共同的尾节点，判断相等的节点就是第一个出现的节点。

 

AC代码：

1 /* 2 struct ListNode { 3     int val; 4     struct ListNode *next; 5     ListNode(int x) : 6             val(x), next(NULL) { 7     } 8 };*/ 9 class Solution {10 public:11     ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {12         map
      
        pmap;13         ListNode *p=pHead1;14         while(p!=NULL)15         {16             pmap[p]=1;17             p=p->next;18         }19         p=pHead2;20         while(p!=NULL)        21         {22             if(pmap[p])23                 return p;24             p=p->next;25         }26         return NULL;27     }28 };