java-7.微软亚院之编程判断俩个链表是否相交 给出俩个单向链表的头指针，比如 h1 ， h2 ，判断这俩个链表是否相交

public class LinkListTest {

	/**
	 * we deal with two main missions:
	 * 
	 * A.
	 * 1.we create two joined-List(both have no loop)
	 * 2.whether list1 and list2 join
	 * 3.print the joinPoint
	 * 
	 * B.
	 * 1.create loop in list1 by itself
	 * 2.whether the list has loop
	 * 3.print the firstNode of loop
	 */
	public static void main(String[] args) {
		MyLinkList list1=new MyLinkList();
		int[] a={1,2,3,4,5,6,7,8,9,10};
		ListNode head1=list1.create(a);
		System.out.print("List1=");
		list1.display();
		
		MyLinkList list2=new MyLinkList();
		int[] b={11,12};
		ListNode head2=list2.create(b);
		ListNode joinPoint=list1.getNodeAt(3);
		ListNode tail02=list2.getTail();
		tail02.next=joinPoint;
		//now list2=11->12->3->4->5 ->6->7->8->9-> 10
		System.out.print("List2=");
		list2.display();
		LinkListTest.isJoined(head1,head2);
		
		//create a loop to find the join-point
		tail02=list2.getTail();
		tail02.next=head2;
		ListNode firsrNodeInLoop=list1.getFirstNodeInLoop(head1);
		System.out.println("The two joinedLink's joinPoint is "+firsrNodeInLoop.data);
		
		//delete the loop
		tail02.next=null;
		
		list1.setLoop(5);//create a loop like following:
		/*now list1=
		 			   ________________
		 			  /			       |
		 1->2->3->4->5 ->6->7->8->9-> 10
		 
		 */
		ListNode meetingPoint=list1.hasLoop(head1);
		if(meetingPoint!=null){
			System.out.println("Now List1  hasLoop,lowPoint&&fastPoint meets at  "+meetingPoint.data);
			firsrNodeInLoop=list1.getFirstNodeInLoop(head1);
			System.out.println("firstNode of Loop is "+firsrNodeInLoop.data);
		}
		
	}
	
	//whether list1 and list2 join
	static void isJoined(ListNode head1,ListNode head2){
		while(head1.next!=null){
			head1=head1.next;
		}
		while(head2.next!=null){
			head2=head2.next;
		}
		if(head1==head2){
			System.out.println("joined");
		}else{
			System.out.println("not joined");
		}
	}
}

class MyLinkList{
	
	private ListNode head;
	
	
	//建立单链表有两种方法：头插法建表和尾插法，后者需多建立一个尾指针
	//这里我用头插法
	public ListNode create(int[] a){
		ListNode firstNode=null;
		//starts with the last element
		for(int i=a.length-1;i>=0;i--){
			ListNode node=new ListNode(a[i]);
			node.next=firstNode;
			firstNode=node;
		}
		head=firstNode;
		return firstNode;
	}
	
	//if hasLoop,return the "Meeting-point".
	public ListNode hasLoop(ListNode head){
		ListNode p1=head;
		ListNode p2=head;
		while(p2!=null&&p2.next!=null){
			p1=p1.next;
			p2=p2.next.next;
			if(p1==p2){
				return p1;
			}
		}
		return null;
	}
	
	//display LinkList's elements while it has no loop
	public void display(){
		ListNode p=head;
		while(p!=null){
			System.out.print(p.data+",");
			p=p.next;
		}
		System.out.println();
	}
	
	//get the a[position]
	public ListNode getNodeAt(int position){
		ListNode node=head;
		while(--position>0){
			node=node.next;
		}
		return node;
	}
	
	//create a loop. Make tail's nextElement is a[i]
	public void setLoop(int i){
		ListNode p=head;
		while(p!=null&&p.next!=null){
			p=p.next;
		}
		ListNode loopPoint=getNodeAt(i);
		p.next=loopPoint;
	}
	
	//p1 traverse from head while p2 from "Meeting-point".When they meets,it's the firstNode of loop
	public ListNode getFirstNodeInLoop(ListNode head){
		ListNode re=null;
		ListNode p1=head;
		ListNode p2=hasLoop(head);
		if(p2!=null){
			while(true){
				p2=p2.next;
				p1=p1.next;
				if(p1==p2){
					re=p1;
					break;
				}
			}
		}
		return re;
	}
	
	//get the last node of LinkList
	public ListNode getTail(){
		ListNode p=head;
		while(p.next!=null){
			p=p.next;
		}
		return p;
	}
	
	public ListNode getHead() {
		return head;
	}
	public void clear(){
		head=null;
	}
	
}

class ListNode{
	int data;
	ListNode next;
	public ListNode(int data){
		this.data=data;
	}
}