题解 | #两个链表的第一个公共结点#

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    // 他给的示例有点奇怪
    // 后来我调试了才看懂的，他给的是三个链表。最后函数收到的是第一个和第三个拼起来的；第二个和第三个拼起来的
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        // 保存头，不然就丢了
        ListNode* head1=pHead1;
        ListNode* head2=pHead2;
        
        // 代码改进，不需要记录长度，一开始就往后走，总有一个先走完。
        // 对于没走完的，后面还剩几个，就代表长了几个
        while(pHead1!=NULL && pHead2!=NULL){
            pHead1=pHead1->next;
            pHead2=pHead2->next;
        }
        // 后面还剩的和它的开头一起开始走
        // 比如说 第一个长度为6，第二个长度为4
        // 那么，当上面那个循环做完后，第一个后面还剩两个就结束了
        // 此时，再扔到循环里面，让他的头和他一起走完两个，最后就是只剩四个了
        // 相比计算两个sum少掉几个循环
        // 时间复杂度都是O(n) 那不会变
        while(pHead1!=NULL){
            head1=head1->next;
            pHead1=pHead1->next;
        }
        while(pHead2!=NULL){
            head2=head2->next;
            pHead2=pHead2->next;
        }
        
        // 保存返回答案的头结点
        ListNode* ans=new ListNode(0);
        
        // 因为要求保存最长，每次都要判断后面是否相等，但是不可能每次都要更新节点
        // temp用来前面是否相等 相等的话，后面如果等，就不用赋值，不相等，就要赋值 并修改temp
        int temp=-1;
        // 现在一样长了，开始做最后的判断
        while(head1!=NULL)
        {
            // 和第一版基本一样 判断temp直接在if判断了，不用分开来写
            if(head1->val==head2->val && temp!=1)
            {
                ans->next=head1;
                temp=1;
            }
            else if(head1->val!=head2->val){
                temp=-1;
                ans->next=NULL;
            }
            head1=head1->next;
            head2=head2->next;
        }
        return ans->next;
    }
};