Thursday, January 5, 2012

Find common nodes from two linked lists using recursion

I have to write a method that returns a linked list with all the nodes that are common to two linked lists using recursion, without loops.
For example,
first list is 2 -> 5 -> 7 -> 10
second list is 2 -> 4 -> 8 -> 10
the list that would be returned is 2 -> 10
I am getting nowhere with this.. What I have been think of was to check each value of the first list with each value of the second list recursively but the second list would then be cut by one node everytime and I cannot compare the next value in the first list with the the second list.

Solution 1: Comparing element by element
This problem depends on the constraints.
The simplest, most naive solution is if you have two elements of size n, you iterate over one list and compare it to every item in the second list.
Solution: O(n2)

Solution 2:  Using Hashset
But of course you can do much better.
Now, if you have a HashSet (or other near-O(1)) data structure available then this is what you can do:
Iterate over one list. Add each element to the set. Iterate over the second list. If the element is in the set then add it to the result list.
Solution: O(n)

Solution 3 : Using merge functionality

Node merge(Node n1, Node n2) {
   IF n1 == null OR n2 == null
      RETURN null
   ELSE IF n1.value == n2.value
      Node dupNode(n1.value);
      dupNode.next = merge(n1.next, n2.next);
      RETURN dupNode;
   ELSE IF n1.value < n2.value
      RETURN merge(n1.next, n2)
   ELSE
      RETURN merge(n1, n2.next)
}

0 comments:

Post a Comment