[数据结构与算法]力扣-剑指 Offer 52. 两个链表的第一个公共节点

Problem Description

Example

Method A

/**
 * 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) {
        int len1=0,len2=0;
        ListNode *p1=headA;
        while(p1!=NULL)
        {
            len1++;
            p1=p1->next;
        }
        ListNode *p2=headB;
        while(p2!=NULL)
        {
            len2++;
            p2=p2->next;
        }
        int count=abs(len1-len2);
        p1=headA,p2=headB;
        if(len2>len1)
        {
            while(count--)
            {
                p2=p2->next;
            }
        }
        else {
            while(count--)
            {
                p1=p1->next;
            }
        }
        while(p1!=NULL)
        {
            if(p1==p2){
                return p1;
            }
            p1=p1->next;
            p2=p2->next;
        }
        return NULL;
    }
};

Method B

/**
 * 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 *p1=headA;
        ListNode *p2=headB;
        unordered_set<ListNode*> map;
        while(p1!=NULL)
        {
            map.insert(p1);
            p1=p1->next;
        }
        while(p2!=NULL)
        {
            if(map.count(p2)) return p2;
            else p2=p2->next;
        }
        return NULL;
    }
};