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-> 10System.out.print("List2=");list2.display();LinkListTest.isJoined(head1,head2);//create a loop to find the join-pointtail02=list2.getTail();tail02.next=head2;ListNode firsrNodeInLoop=list1.getFirstNodeInLoop(head1);System.out.println("The two joinedLink's joinPoint is "+firsrNodeInLoop.data);//delete the looptail02.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 joinstatic 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 elementfor(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 looppublic 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 looppublic 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 LinkListpublic 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;}}