LeetCode探索の旅(37)-160両チェーンテーブルの交差点

今日引き続きLeetCodeを塗って、第160題、2つのチェーンテーブルの交差点を求めます.
解析:交差点である以上,Yの形状に似た一定の長さの同じノードが後方から前方に存在するはずであるが,チェーンテーブルの特徴は後方から前方へ遍歴できないことであり,前方から後方へ遍歴するしかない.まず、2つのチェーンテーブルの長さをそれぞれ計算し、長さの差を求め、長いチェーンテーブルは、まず行った後から1つの長さの差の長さを遍歴し、2つのチェーンテーブルは、2つのチェーンテーブルのノードが等しくなるまで、同時に後ろに遍歴し続け、交差ノードである.
質問:1、特殊な場合、チェーンテーブルが空の場合.2、チェーンテーブルの長さを求める;
コードを添付:

/**
 * 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;
        int length1=0;
        int length2=0;
        ListNode* A=headA;
        ListNode* B=headB;
        while(A!=NULL)
        {
            length1++;
            A=A->next;
        }
        while(B!=NULL)
        {
            length2++;
            B=B->next;
        }
        int s;
        if(length1>length2)
        {
            s=length1-length2;
            for(int i=0;inext;
            }
            while(headA!=headB)
            {
                
                headA=headA->next;
                headB=headB->next;
                if(headA==NULL&&headB==NULL)
                    return NULL;
            }
            return headA;
        }
        else
        {
            s=length2-length1;
            for(int i=0;inext;   
            }
            while(headA!=headB)
            {
                
                headA=headA->next;
                headB=headB->next;
                if(headA==NULL&&headB==NULL)
                    return NULL;
            }
            return headB;
        }

    }
};

最適化されたコード:

/**
 * 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;
        int length1=length(headA);
        int length2=length(headB);
        int s=length1-length2;
        if(s>0)
            return intersection(headA,headB,s);
        else
            return intersection(headB,headA,-s);

    }
    ListNode* intersection(ListNode *headA,ListNode *headB,int s)
    {
        while(s--)
        {
            headA=headA->next;
        }
        while(headA!=headB)
        {
            headA=headA->next;
            headB=headB->next;
            if(headA==NULL&&headB==NULL)
                return NULL;
        }
        return headA;
    }
    int length(ListNode * head)
    {
        int s=0;
        while(head!=NULL)
        {
            s++;
            head=head->next;
        }
        return s;
    }
};

もう1つの方法は、2つのチェーンテーブルを同時に後方に巡回することができ、1つのチェーンテーブルがすべてのノードを巡回した後、別のチェーンテーブルのヘッダノードにジャンプして後方に巡回し始め、2つのポインタが出会ったとき、ノードが交差ノードであることを意味します.