fork download
copy 
  1. /**
  2.  * Linked List Node
  3.  * @author Prateek
  4.  */
  5. class Node {
  6.  
  7. 	public int data;
  8. 	public Node next;
  9. 	public Node prev;
  10.  
  11. 	public Node(int data){
  12. 		this.data=data;
  13. 	}
  14.  
  15. 	public String toString(){
  16. 		return ""+data;
  17. 	}
  18. }
  19. /**
  20.  * Find the intersection of Linked Lists
  21.  * @author Prateek Rathore
  22.  */
  23. class YIntersection {
  24. 	/**
  25. 	 * Detect Intersection of linked Lists
  26. 	 * @return null if no intersection , else return the intersecting node
  27. 	 */
  28. 	public static Node detectIntersection(Node head1, Node head2){
  29. 		int len1=0, len2=0,offset =0;
  30. 		Node temp1,temp;
  31.  
  32. 		//Step1
  33. 		//==== length calculation starts
  34. 		temp = head1;
  35. 		while(temp!=null){
  36. 			temp=temp.next;
  37. 			len1++;
  38. 		}
  39.  
  40. 		temp=head2;
  41. 		while(temp!=null){
  42. 			temp=temp.next;
  43. 			len2++;
  44. 		}
  45.  
  46. 		//==== length calculation ends
  47.  
  48. 		//Step 2
  49. 		//==== Pointer advancement on the basis of offset starts
  50. 		offset = len1 > len2 ? (len1 - len2) : (len2 - len1) ;
  51. 		if(len1>len2){
  52. 			temp = head1;
  53. 			temp1= head2;
  54. 		}
  55. 		else {	
  56. 			temp = head2;
  57. 			temp1 = head1;
  58. 		}
  59.  
  60. 		while(offset > 0){
  61. 			temp=temp.next;
  62. 			offset--;
  63. 		}
  64.  
  65. 		//==== Pointer advancement on the basis of offset ends
  66.  
  67. 		//Step 3
  68. 		// Final Step of Running the pointers
  69. 		while(temp!=null && temp1!=null){
  70. 			if(temp1 == temp)
  71. 			   return temp;
  72.  
  73. 			temp=temp.next;
  74. 			temp1=temp1.next;
  75. 		}
  76. 		return null;
  77. 	}
  78.  
  79. 	public static void main(String[] args) {
  80.  
  81. 		Node head= new Node(4);
  82. 		head.next= new Node(3);
  83. 		head.next.next= new Node(2);
  84. 		head.next.next.next= new Node(1);
  85.  
  86. 		Node head1= new Node(18);
  87. 		head1.next= new Node(17);
  88. 		head1.next.next = head;  //deliberate joining
  89.  
  90. 		Node head2= new Node(14);
  91. 		head2.next= new Node(13);
  92. 		head2.next.next= new Node(12);
  93. 		head2.next.next.next= new Node(11);
  94. 		head2.next.next.next.next=head;   //deliberate joining
  95.  
  96. 		//Prints the intersecting Node
  97. 		System.out.println(detectIntersection(head1,head2));
  98. 	}
  99. }
  100.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/XR9Fdz
Linked List: Y Intersection
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!