Example:
Input :
Output : 4
Algorithm
1) Find lengths of both lists
2) take the difference d of the lengths
3) make d steps in longer list
4) step in both lists in parallel until links to next node match
Implementation
class FindTheMergingPoingInGiven2LinkedList{
static class LinkedList{
int data;
LinkedList next = null;
public LinkedList(int data){
this.data = data;
}
public void insertAtEnd(int data){
LinkedList head = this;
LinkedList newNode = new LinkedList(data);
if(head == null){
head = newNode;
return;
}
while(head.next != null){
head = head.next;
}
head.next = newNode;
}
public void print(LinkedList head){
while(head != null){
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
//time : O(N)
public static int length(LinkedList head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}
public static LinkedList findMergingPoint(LinkedList head, LinkedList head2){
//Base condition
if(head == null && head2 == null)
return null;
int length = length(head); //length of first list
int length2 = length(head2); //length of second list
int diff; //difference d of the lengths
LinkedList bigList, smallList;
if(length > length2){
diff = length - length2;
bigList = head;
smallList = head2;
}else{
diff = length2 - length;
bigList = head2;
smallList = head;
}
//make d steps in longer list
for(int i = 0; i < diff; i++)
bigList = bigList.next;
//make step in both lists in parallel until links to next node match
//or null
while(bigList != null && smallList != null){
if(bigList == smallList)
return bigList;
bigList = bigList.next;
smallList = smallList.next;
}
return null;
}
}
public static void main(String []args){
LinkedList head = new LinkedList(1);
head.insertAtEnd(2);
head.insertAtEnd(3);
head.insertAtEnd(4);
head.insertAtEnd(5);
head.insertAtEnd(6);
LinkedList head2 = new LinkedList(7);
head2.insertAtEnd(8);
head2.next.next = head.next.next.next; //merging the lists
head2.print(head);
head2.print(head2);
LinkedList mergePoint = LinkedList.findMergingPoint(head, head2);
System.out.println(mergePoint.data);
}
}
Time Complexity: O(max(m, n))
Space Complexity : O(1)
Input :
Output : 4
Algorithm
1) Find lengths of both lists
2) take the difference d of the lengths
3) make d steps in longer list
4) step in both lists in parallel until links to next node match
Implementation
class FindTheMergingPoingInGiven2LinkedList{
static class LinkedList{
int data;
LinkedList next = null;
public LinkedList(int data){
this.data = data;
}
public void insertAtEnd(int data){
LinkedList head = this;
LinkedList newNode = new LinkedList(data);
if(head == null){
head = newNode;
return;
}
while(head.next != null){
head = head.next;
}
head.next = newNode;
}
public void print(LinkedList head){
while(head != null){
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
//time : O(N)
public static int length(LinkedList head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}
public static LinkedList findMergingPoint(LinkedList head, LinkedList head2){
//Base condition
if(head == null && head2 == null)
return null;
int length = length(head); //length of first list
int length2 = length(head2); //length of second list
int diff; //difference d of the lengths
LinkedList bigList, smallList;
if(length > length2){
diff = length - length2;
bigList = head;
smallList = head2;
}else{
diff = length2 - length;
bigList = head2;
smallList = head;
}
//make d steps in longer list
for(int i = 0; i < diff; i++)
bigList = bigList.next;
//make step in both lists in parallel until links to next node match
//or null
while(bigList != null && smallList != null){
if(bigList == smallList)
return bigList;
bigList = bigList.next;
smallList = smallList.next;
}
return null;
}
}
public static void main(String []args){
LinkedList head = new LinkedList(1);
head.insertAtEnd(2);
head.insertAtEnd(3);
head.insertAtEnd(4);
head.insertAtEnd(5);
head.insertAtEnd(6);
LinkedList head2 = new LinkedList(7);
head2.insertAtEnd(8);
head2.next.next = head.next.next.next; //merging the lists
head2.print(head);
head2.print(head2);
LinkedList mergePoint = LinkedList.findMergingPoint(head, head2);
System.out.println(mergePoint.data);
}
}
Time Complexity: O(max(m, n))
Space Complexity : O(1)
No comments:
Post a Comment