LeetCode160。リンクリストを交差させる

この質問の練習は、より泥棒なので、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;
 }
};