当前位置:首页 > 开发 > 编程语言 > Java > 正文

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

发表于: 2012-01-14   作者:bylijinnan   来源:转载   浏览:
摘要: 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 join

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;
	}
}



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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
个人认为,算法永远是王道。此处将截取编程之美这本书上经典的算法题,以飨各位。 同时,除了旁征博
题目:编程判断俩个链表是否相交,给出俩个单向链表的头指针,比如h1,h2,判断这俩个链表是否相交。
判断两个链表是否相交,《编程之美》给出了以下方法: 1.判断第一个链表的每个节点是否在第二个链表
这个是《编程之美》里面的一个题目,给出两个单项链表的头指针,h1、h2判断这2个链表是否相交? 【
问题: 给出两个单向链表的头指针,而两个链表都可能带环,判断这两个链表是否相交,并且给出他们相
在前面一篇文章中讲了如何判断一个链表中有环,如果有环的话,又如何判断出环出现在哪里 http://blo
先看看原题:《编程之美》3.6编程判断两个链表是否相交,原题假设两个链表不带环。 注:位于(*)符号
  先看看原题:《编程之美》3.6编程判断两个链表是否相交,原题假设两个链表不带环。   为了防
  先看看原题:《编程之美》3.6编程判断两个链表是否相交,原题假设两个链表不带环。 注:位于(*)
请参照书P233-235. 这道题让我联想起几道关于单向链表的经典题目: 如果判断一个单项链表是否存在环
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号