解题思路:若两条链表开头不同的部分分别为a和b,重合部分的长度为c,则当两个结点相遇时,走过的路程相等,均为a+b+c。所以定义两个结点,若遍历完则从头遍历。相遇时一定为第一个公共结点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
ListNode*p=headA;//定义指针p为第一个链条的头结点A
ListNode*q=headB;//定义指针q为第一个链条的头结点B
while(p!=q)//当p和q没有重合时
{
if(p)p=p->next;//p向后移动
else(p)=headB;//若为空,即遍历完一条链表,则移动到另一条链表从头遍历
if(q)q=q->next;//同理
else(q)=headA;
}
return p;//当p==q时,相遇,即为第一个公共结点。返回指针p
}
};