[C++知识库]力扣-面试题 02.07. 链表相交（C++）- 双指针及unordered_set两种解法

题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
题目如下：



第一种的思路（注：第二种为哈希，易理解，故不放思路）：

/**
 * 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) {
        //解法一：空间复杂度：O(1)
        int lenA=0,lenB=0;
        ListNode* ha=headA;
        ListNode* hb=headB;
        while(ha!=NULL){
            ha=ha->next;
            lenA++;
        }
        
        while(hb!=NULL){
            hb=hb->next;
            lenB++;
        }            

        ha=headA;
        hb=headB;
        if(lenA<lenB){//目标：A中为长的，B中为短的
            swap(headA,headB);
            swap(lenA,lenB);
        }

        for(int i=0;i<lenA-lenB;i++)
            headA=headA->next;

        while(headA!=NULL){
            if(headA==headB) return headA;
            headA=headA->next;
            headB=headB->next;
        }

        return NULL;

        /* //解法二：空间复杂度：O(m+n)
        ListNode* ha=headA;
        ListNode* hb=headB;
        unordered_set<ListNode*> hashset;

        while(ha!=NULL){
            hashset.insert(ha);
            ha=ha->next;
        }

        while(hb!=NULL){
            if(hashset.count(hb)!=0){
                return hb;
            }
            hb=hb->next;
        }

        return NULL;
        */
    }
};