21 Dec 2013

LinkedList : Y Intersection

Problem Statement: 
         Detect the Y- Intersection of the two given Linked List

Fig: Intersecting Linked Lists

Solution:

Full Source Code : LINK

The steps Involved in the above problem are:
1. Calculate lengths of the linked list
2. Advancement in the linked list which is larger in length(i.e. advance by the offset difference of the two lengths).
3. Traverse


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
  * Detect Intersection of linked Lists
  * @return null if no intersection , else return the intersecting node
  */
 public static Node detectIntersection(Node head1, Node head2){
  int len1=0, len2=0,offset =0;
  Node temp1,temp;
  
  //Step1
  //==== length calculation starts
  temp = head1;
  while(temp!=null){
   temp=temp.next;
   len1++;
  }

  temp=head2;
  while(temp!=null){
   temp=temp.next;
   len2++;
  }

  //==== length calculation ends

  //Step 2
  //==== Pointer advancement on the basis of offset starts
  offset = len1 > len2 ? (len1 - len2) : (len2 - len1) ;
  if(len1>len2){
   temp = head1;
   temp1= head2;
  }
  else { 
   temp = head2;
   temp1 = head1;
  }
  
  while(offset > 0){
   temp=temp.next;
   offset--;
  }
  
  //==== Pointer advancement on the basis of offset ends
  
  //Step 3
  // Final Step of Running the pointers
  while(temp!=null && temp1!=null){
   if(temp1 == temp)
      return temp;
   
   temp=temp.next;
   temp1=temp1.next;
  }
  return null;
 }
 

Please point out if any mistakes or suggestions in the code.
Happy Coding :!!1

1 comment: