(剣指Offer)面接問題37:2つのチェーンテーブルの最初の共通ノード

タイトル:
2つのチェーンテーブルを入力し、最初の共通ノードを見つけます.
チェーンテーブルノードの定義は次のとおりです.

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){};
};

考え方:
1、暴力法
1番目のチェーンテーブルを巡回し、1つのノードに巡回するたびに、2番目のチェーンテーブルで順次巡回します.2番目のチェーンテーブルに1つのノードがノードと同じであれば、2つのチェーンテーブルがこのノードで一致していることを示します.つまり、1番目の共通ノードです.
時間複雑度:O(mn)
2、スタック法
2つのチェーンテーブルに共通のノードがある場合、最初の共通のノードからチェーンの最後まで、すべてのノードが一致しています.2つのチェーンテーブルの末尾から前に比較すると、最後の同じノードが最初の共通のノードになります.
しかし、単一チェーンテーブルには後続のポインタしかなく、戻ることができません.私たちはすぐにスタックを思い出し、2つのチェーンテーブルのノードをそれぞれ2つのスタックに入れることができます.このように、2つのテールポインタはスタックの頂上にあり、次にスタックの頂上のポインタが同じかどうかを比較します.もしそうであれば、スタックの頂上をポップアップし、最後の同じノードが見つかるまで次のスタックの頂上を比較します.
時間複雑度:O(m+n)、空間複雑度:O(m+n)
3、2つのポインタ
まず、2つのチェーンテーブルA,Bをそれぞれ巡回し、lenA,lenBのようなそれぞれの長さを得、lenA>lenBと仮定し、その後、AポインタをlenA-lenBに先に歩かせ、次に2つのポインタを一緒に歩いて、出会いが最初の共通ノードを見つけるまで歩いた.
時間複雑度:O(m+n)
コード:
ここでは方法3のみを実現する.

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){};
};

unsigned int GetListLength(ListNode* pHead){
    unsigned int len=0;
    while(pHead!=NULL){
        len++;
        pHead=pHead->next;
    }
    return len;
}

ListNode* FindFirstCommonNode(ListNode* pHead1,ListNode* pHead2){
    unsigned int len1=GetListLength(pHead1);
    unsigned int len2=GetListLength(pHead2);
    ListNode* pLong=pHead1;
    ListNode* pShort=pHead2;
    unsigned lenDiff=len1-len2;
    if(len1<len2){
        pLong=pHead2;
        pShort=pHead1;
        lenDiff=len2-len1;
    }

    for(unsigned int i=0;i<lenDiff;i++)
        pLong=pLong->next;

    while(pShort!=NULL && pLong!=NULL && pShort!=pLong){
        pShort=pShort->next;
        pLong=pLong->next;
    }

    ListNode* pFirstCommonNode=pLong;

    return pFirstCommonNode;
}

オンラインテストOJ:
http://www.nowcoder.com/books/coding-interviews/6ab1d9a29e88450685099d45c9e31e46?rp=2
ACコード:

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
        int len1=GetListLength(pHead1);
        int len2=GetListLength(pHead2);
        ListNode* pLong=pHead1;
        ListNode* pShort=pHead2;
        int lenDiff=len1-len2;
        if(len1<len2){
            pLong=pHead2;
            pShort=pHead1;
            lenDiff=len2-len1;
        }
        
        for(int i=0;i<lenDiff;i++)
            pLong=pLong->next;
        
        while(pLong!=NULL && pShort!=NULL && pLong!=pShort){
            pLong=pLong->next;
            pShort=pShort->next;
        }
        
        ListNode* pFirstCommonNode=pLong;
        return pFirstCommonNode;
    }
    
    unsigned int GetListLength(ListNode* pHead){
        unsigned int len=0;
        while(pHead!=NULL){
            ++len;
            pHead=pHead->next;
        }
        return len;
    }
};