チェーンテーブルの交差の判断

1.チェーンテーブルの交差を判断し、交差する最初のノードを探し出す
   

package org.jyjiao;

import java.util.*;

public class IsLinkCross {

	/*
	 *     ：      ,              1： 1.
	 *        ，    ，         ，             ，       。 2.
	 *         length，     ，          (lengthMax-lengthMin) ，
	 *           ，    ，                   。
	 */
	public String isLinkListCross1(LinkedList<String> listA,
			LinkedList<String> listB) {
		int ret = -1;
		int lenA = 0, lenB = 0;
		Iterator<String> itA = listA.iterator();
		while (itA.hasNext()) {
			itA.next();     //    ，     
			lenA++;
		}
		Iterator<String> itB = listB.iterator();
		while (itB.hasNext()) {
			itB.next();     //    ，     
			lenB++;
		}
		itA = listA.iterator();
		itB = listB.iterator();
		int wait;
		if (lenA >= lenB) {
			wait = lenA - lenB;
			for (int i = 0; i < wait; i++) {
				itA.next();
			}
		} else {
			wait = lenB - lenA;
			for (int i = 0; i < wait; i++) {
				itB.next();
			}
		}
		while (itA.hasNext() && itB.hasNext()) {
			String strA = itA.next();
			String strB = itB.next();
			if (strA.equals(strB)) {
				return strA;
			}
			wait++;

		}

		return null;
	}

	/*
	 *     ：      ,              2： 1.        ，    ，               2.
	 *          ，             ，                  ，       ；               
	 */
	public String isLinkListCross2(LinkedList<String> listA,LinkedList<String> listB){
		String ret=null;
		HashSet<String> hsetA=new HashSet<String>();
		Iterator<String> itA=listA.iterator();
		
		while(itA.hasNext()){
			String str=itA.next();
			hsetA.add(str);
		}
		
		int startIndexB;
		for(int i=0;i<listB.size();i++){
			if(hsetA.contains(listB.get(i))){
				startIndexB=i;
				int startIndexA=listA.indexOf(listB.get(i));
				while(startIndexA<listA.size()&& startIndexB<listB.size()){
					if(listA.get(startIndexA).equals(listB.get(startIndexB))){
						startIndexA++;
						startIndexB++;
							
					}else{
						i=startIndexB;
						break;
					}
				}
				if(startIndexA==(listA.size())){
					return listB.get(i);
				}
			}
		}
		

		return ret;
		
	}

	public static void main(String[] args) {
		LinkedList<String> listA = new LinkedList<String>();
		LinkedList<String> listB = new LinkedList<String>();
		listA.add("one");
		listA.add("two");
		listA.add("three");
		listA.add("four");
		listA.add("five");
		listA.add("six");

		listB.add("seven");
		listB.add("eight");
		listB.add("three");
		listB.add("four");
		listB.add("five");
		listB.add("six");

//		IsLinkCross test1 = new IsLinkCross();
//		String retStr = test1.isLinkListCross1(listA, listB);
//		if (retStr == null) {
//			System.out.println("no cross point");
//		} else {
//			System.out.println("lists cross at : " + retStr);
//		}

		IsLinkCross test2 = new IsLinkCross();
		String retStr = test2.isLinkListCross2(listA, listB);
		if (retStr == null) {
			System.out.println("no cross point");
		} else {
			System.out.println("lists cross at : " + retStr);
		}

	}

}

 
 
 
2.チェーンテーブルにループがあると判断
アルゴリズム1:ハヒ法,類似問題1のアルゴリズム2
アルゴリズム2:最も古典的な方法は2つのポインタで、1つは毎回次の別のステップを指して2つです.つまり、次の次のステップを指して、彼ら2人を最初から1つ前から1つ後ろに遍歴させます.ループがなければ、最後に遅い者が速い者を追いかけます.ループがあれば、最後に速い者が「追いつく」遅い者を指します.ループの中で速い者は追い越すことができるからです.
 
 
3.関数を書く中間ノードの位置を素早く見つける

package org.jyjiao;
import java.util.*;
public class LinkMid {
	public String getMidItem(LinkedList<String> list){
		String retStr=null;
		int fast=0,slow=0;
		Iterator<String> it1=list.iterator();
		Iterator<String> it2=list.iterator();
		int i=0,j=0;
		while(it1.hasNext()){
			it1.next();
			if(it1.hasNext()){
				it1.next();
			}else{
				retStr=it2.next();
				break;
			}
			retStr=it2.next();
		}
		
		return retStr;
	}
	
	public static void main(String[] args){
		LinkedList<String> list=new LinkedList<String>();
		list.add("1");
		list.add("2");
		list.add("3");
		list.add("4");
		list.add("5");
		LinkMid mid=new LinkMid();
		String ret=mid.getMidItem(list);
		System.out.println("mid item is:"+ret);
	}
	

}

    
 
 
 
 
5.チェーンテーブルの最後からk番目のノードを探し出す
アルゴリズムの思想は中間のノードを求めることに似ています