【九度OJ 1505】|【剣指offer 37】2つのチェーンテーブルの最初の共通ノード

タイトルの説明:
2つのチェーンテーブルを入力し、最初の共通ノードを見つけます.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力される第1の動作の2つの整数mおよびn(1<=m、n<=1000):入力する2つのチェーンテーブルの要素の数を表す.次の2行は、最初の動作の最初のチェーンテーブルのすべての要素で、中央はスペースで区切られています.2番目の動作2番目のチェーンテーブルのすべての要素は、スペースで区切られています.
出力:
各テストケースに対応して、2つのチェーンテーブルの最初の共通ノードの値を出力します.2つのチェーンテーブルに共通のノードがない場合は、「My God」が出力されます.
サンプル入力:

5 4
1 2 3 6 7
4 5 6 7
3 3
1 5 7
2 4 7
2 3
1 3
4 5 6

サンプル出力:

6
7
My God

解析:
この問題を見て、第一反応は蛮力法です:第一鎖表の上で順番に各結点を遍歴します.1つのノードを巡回するたびに、2番目のチェーンテーブルに各ノードを順次巡回します.このとき、2つのチェーンテーブルのノードが同じである場合、2つのチェーンテーブルが重なることを示し、共通のノードが見つかりました.第1のチェーンテーブルの長さがm,第2のチェーンテーブルの長さがnの場合,この方法の時間的複雑さはO(mn)であることは明らかである.
次に,線形時間複雑度のアルゴリズムを探してみた.まず問題を簡略化します.2つの一方向チェーンテーブルに共通のノードがあるかどうかをどのように判断しますか.前述したように、2つのチェーンテーブルに共通のノードがある場合、共通のノードの後にあるすべてのノードは一致します.では、それらの最後のノードは必ず重なる.そこで,2つのチェーンテーブルが重なり合う部分があるかどうかを判断し,それぞれ2つのチェーンテーブルを最後のノードまで遍歴すればよい.2つのテールノードが同じであれば、それらが重なることを示します.そうでなければ、2つのチェーンテーブルには共通のノードがありません.
上記の考え方では,2つのチェーンテーブルからテールノードまで順次遍歴する場合,2つのチェーンテーブル上で同時にテールノードに到達することは保証できない.これは、2つのチェーンテーブルが必ずしも同じ長さではないからです.しかし、あるチェーンテーブルが別の長いl個のノードよりも長いと仮定すると、私たちはまず長いチェーンテーブル上でl個のノードを遍歴し、その後同期して遍歴し、この時私たちは同時に最後のノードに着くことを保証することができます.2つのチェーンテーブルは、最初の共通ノード試験からチェーンテーブルの末尾ノードまで、この部分が重なるためです.したがって、それらも同時に第1の共通ノードに到着したに違いない.そこで遍歴では,最初の同じノードが最初の共通のノードである.
この考え方では,まず2つのチェーンテーブルをそれぞれ遍歴してそれらの長さを求め,2つの長さの差を求めた.長いチェーンテーブルを何回か巡回した後、2つのチェーンテーブルを同期して巡回し、同じノードが見つかるか、チェーンテーブルが終わるまで待機します.このとき,第1のチェーンテーブルの長さがm,第2のチェーンテーブルの長さがnの場合,この方法の時間的複雑度はO(m+n)である.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
 
/**
 *  
 * 2014 3 17  22:09:38
 * @author aqia358
 *
 */
public class Main {
 
    static class Node{
        public int value;
        public Node next = null;
    }
    public static void find(Node a, Node b, int m, int n){
        Node l = new Node();
        Node s = new Node();
        int p = 0;
        if(m > n){
            l = a;
            s = b;
            p = m - n;
        }else{
            l = b;
            s = a;
            p = n - m;
        }
        while(p > 0){
            p--;
            l = l.next;
        }
        while(l.next != null && l.value != s.value){
            l = l.next;
            s = s.next;
        }
        if(l.next == null)
            System.out.println("My God");
        else
            System.out.println(l.value);
    }
     
     
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        while(st.nextToken() != st.TT_EOF){
            int m = (int) st.nval;
            st.nextToken();
            int n = (int) st.nval;
            Node a = new Node();
            Node a1 = a;
            Node b = new Node();
            Node b1 = b;
            for(int i = 0; i < m; i++){
                st.nextToken();
                a1.value = (int) st.nval;
                a1.next = new Node();
                a1 = a1.next;
            }
            for(int j = 0; j < n; j++){
                st.nextToken();
                b1.value = (int) st.nval;
                b1.next = new Node();
                b1 = b1.next;
            }
            Main.find(a, b, m, n);
        }
    }
 
}
 
/**************************************************************
    Problem: 1505
    User: aqia358
    Language: Java
    Result: Accepted
    Time:910 ms
    Memory:27504 kb
****************************************************************/