Yahoo Interview Question
Software Engineer / Developerspublic linkedlist intersection(linkedlist head1,linkedlist head2){
Node current1 = head1;
Node current2 = head2;
linkedlist returnlist = new linkedlist();
while(current1 !=null && current2 !=null){
if(current1.data==current2.data)
returnlist.add(new node(current1.data))
else if(current1.data>current2.data)
current2 = current2.next
else current1 = current1.next
}
return returnlist ;
}
Here is sample programme to get intersection os two sorted list
private Node getIntersectedLinkedList(Node first, Node second){
Node ptr = first;
Node ptr1 = second;
Node previous = null;
Node firstIntersectedNode = null;
while (ptr != null) {
ptr1=second;
while (ptr1!= null && ptr.getValue() != ptr1.getValue() ) {
ptr1 = ptr1.getNext();
}
if(ptr1 !=null){
Node node = new Node();
if (firstIntersectedNode == null) {
firstIntersectedNode = node;
}
node.setValue(ptr.getValue());
if (previous != null) {
previous.setNext(node);
}
previous = node;
}
ptr = ptr.getNext();
}
return firstIntersectedNode;
}
@S
- Manish September 18, 2010The question itself says that you need to create a new linked list.
Solution:
Keep two pointers at the start of the both linked list.
1. Compare two values. If they are equal copy this value to new linked list.
2. if values are not equal then move the pointer of the linked list having the lower value to its next value .
go to step 1. untill any linked list ends.