この質問の練習は、より泥棒なので、2つのポインタp、qは、2つのチェーンの先頭を指し、その後、2つのポインタが空でない限り、異なるの場所を指しているように、それらは、ポインタが空になったとき、それは他のチェーンテーブルの先頭を指し、戻って移動されます。
例えば、上の図で、交差する部分、2つのリンクリストの長さをaとb、交差するリンクの後の長さをcとします。
次に、pポインタはa + cの長さで2番目のヘッドheadBを指し、qポインタはb + cの長さで最初のヘッドheadAを指します。
その後、2つのポインターはbとaの長さを行き来し、a + b + cを経て、ようやく2つのポインターが出会います。これは2つのリンクリストが交点を持つ場合です。
この歩き方は、2つのリンクリストが交差しない場合にも成り立ちます。
たとえば、上の図は、pは、最初のチェーンテーブルを歩いて、2番目のチェーンテーブルのヘッドBに歩いて、qは、2番目のチェーンテーブルを歩いて、最初のチェーンテーブルのヘッドAに歩いて、彼らは右の各bのステップとaのステップは、両方のNULLに、NULLああ、2つのポインタがNULLを指していることに注意してください、同じ場所を指すとみなすことができるので、戻り値はpです。
コードは以下の通り：
/**
* 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) {
auto p = headA, q = headB;
while(p != q) {
if(p != NULL) {
p = p -> next;
} else {
p = headB;
}
if(q != NULL) {
q = q -> next;
} else {
q = headA;
}
}
return p;
}
};
