剑指offer36两个链表的第一个公共结点

剑指offer36
其他博客解读参考
1、直接双重循环比较
个人答案

//直接两重循环比较
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* temp=pHead2;
        while(pHead1)
        {
            pHead2=temp;
            while(pHead2)
            {
                if(pHead1==pHead2)
                    return pHead1;
                 pHead2=pHead2->next;
            }
            pHead1=pHead1->next;
        }
        return nullptr;
    }

2、差值法（较长优先走）：两个链表在公共节点之前长度不一定一致，所以不能同时遍历比较。可以让长的先走n-m步，然后再同时走，进行比较
个人答案

//双指针法1：两个链表在公共节点之前长度不一定一致，所以不能同时遍历比较。
//          可以让长的先走n-m步，然后再同时走，进行比较
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int n=0;
        int m=0;
        ListNode* head1=pHead1;
        ListNode* head2=pHead2;
        while(pHead1)
        {
            ++n;
            pHead1=pHead1->next;
        }
         while(pHead2)
        {
            ++m;
            pHead2=pHead2->next;
        }
        if(n>m)
        {
            int x=n-m;
            while(x--)
            {
                head1=head1->next;
            }
        }
        else if(m>n)
        {
            int x=m-n;
            while(x--)
            {
                head2=head2->next;
            }
        }
        while(head1&&head2)
        {
            if(head1==head2)
                return head1;
            head1=head1->next;
            head2=head2->next;
        }
        return nullptr;
    }

2、双指针法
个人答案
两个链表公共的前缀部分可能不一致，可以使用差值法，长的提前走完差值长度，但需要多次遍历.
也可以将两个链表接在一起长度均为m+n,即相当于两个链表分别加上对方链表作为自己的前缀，从而使得，两链表公共部分之前的前缀长度一致，可以同时走到公共部分。
注意：
1、若两链表长度一致，在附加前缀部分就可以找出公共点（无论有无公共点）
2、a+b之后，两个链表长度一致，所以有公共节点,返回公共节点，遍历次数<=m+n;无公共节点，尾部nullptr也可以看作虚拟的公共节点，返回虚拟公共节点nullptr,遍历m+n+1次

class Solution {
public:
//双指针法：两个链表公共的前缀部分可能不一致，可以使用差值法，长的提前走完差值长度，
//         但需要多次遍历.
//         也可以将两个链表接在一起长度均为m+n,即相当于两个链表分别加上对方链表作为自己的前缀
//         从而使得，两链表公共部分之前的前缀长度一致，可以同时走到公共部分。
//注意：1、若两链表长度一致，在附加前缀部分就可以找出公共点（无论有无公共点）
//     2、a+b之后，两个链表长度一致，所以有公共节点,返回公共节点，遍历次数<=m+n;
//        无公共节点，尾部nullptr也可以看作虚拟的公共节点，返回虚拟公共节点nullptr,遍历m+n+1次
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* head1=pHead1;
        ListNode* head2=pHead2;
        while(head1!=head2)
        {
            head1=head1?head1->next:pHead2;//head1==null时，换上另一个链表
            head2=head2?head2->next:pHead1;
        }
        return head1;
    }
};