Intersection of Two Linked Lists leetcode

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return  null .
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
タイトルの意味は2つのチェーンテーブルの交差点を見つけて、そのノードに戻って、もしないならば、NULLに戻ります
考え方:
1、暴力法は直接に1つずつ比較して2つの循環時間の複雑度でN*M N Mはそれぞれ2つのチェーンテーブルの長さである.
2、ハッシュ表法:チェーン表Aを遍歴し、ノードをハッシュ表に記憶する.次に、チェーンテーブルBを巡回し、B内の各ノードについてハッシュテーブルを検索し、ハッシュテーブルで見つかった場合、交差が始まるノードであることを示す.時間的複雑度O(N＋M),空間的複雑度O(N)またはO(M).
3、双指針法:2つの針を定義し、それぞれheadAとheadBを指し、それぞれ2つの鎖結点個数(長さ)を求め、その後temp=abs(numA-numB)で両者の差を求め、長い鎖(max(numA,numB))を先にtempステップさせ、それから長い鎖の現在位置と短い鎖の頭部を一緒に後ろに遍歴し、同じ
以上のように

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

長鎖がBであるため、Bはabs(6-5)=1ステップ長鎖の現在位置がb 2であり、Aはa 1の2つのポインタから一緒に後ろに進む
ダブルポインタメソッドの変形方法:
上はまずA Bを1回遍歴する必要がありますが、初めて遍歴したときにAとBを一緒に行かせたら、NULLが1つあれば止まります.
では、この時点で短鎖はもう終わり、長鎖は短鎖の長さを歩き、残りの長さは2本の鎖の長さの差となる
以上のように

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

このときBの現在位置はc 3であり、次にAを指すポインタがb 1(歩き切れていない頭部)を指す現在位置とAを指すポインタが同時に後ろに進み、現在位置がNULLを指して終了し、Aを指すポインタがb 2を指す.すなわち、先に求めた長さ差歩の位置を指し、その後、残りの歩き終わりに従って交点を見つける
コードは次のとおりです.

<span style="font-size:18px;">/**
 * 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) {
        
        if(headA==NULL||headB==NULL)
            return NULL;
        ListNode *p,*q;
        p=headA;
        q=headB;
        
        int numA=0;  //  numA    headA      
        int numB=0;//  numB    headB      
        
        while(p)
        {
            ++numA;
            p=p->next;
        }
        while(q)
        {
            ++numB;
            q=q->next;
        }
        
        
        p=headA;
        q=headB;
        int temp=abs(numA-numB);
        if(numA>numB) //      ，        |numA-numB|  
        {
            while(temp>0)
            {
                p=p->next;
                --temp;
            }
        }
        else
        {
            while(temp>0)
            {
                q=q->next;
                --temp;
            }
        }
        while(p&&q)  //        ，                 
        {
            if(p==q)
                return p;
            p=p->next;
            q=q->next;
        }
        return NULL;
        
    }
};</span>