Find common nodes from two linked lists using recursion

Question

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. I hope this makes sense...

Can anyone help?

Answer 1

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(n²)

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)

Answer 2

This question only has weight in it if the values in each list are sorted. If that's the case, then this will find duplicates recursively (in pseudocode)

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)
}

Given a list of length L1 and L2, this will merge them in O(L1 + L2). It does so non-destructively, by creating new nodes for the duplicates. You can easily modify it to "steal" from one of the lists if you wish.

Answer 3

If you do not care about duplicates using Set's built-in retainAll() method is an easy solution.

  List<T> list1 = ...; // The smaller list
  List<T> list2 = ...; 

  ...
  final Set<T> s1 = new HashSet<T>(list1);
  s1.retainAll(list2); 
  // Try s1.retainAll(new HashSet<T>(list2)); if the lists are really bug

  final List<T> solution = new LinkedList(s1);

Answer 4

There are many ways to interpret the question. Are we looking for an intersection of the sets represented by the lists, or are we looking for a longest common subsequence? are the lists always sorted?

In my recursive solution, I assume that we are looking for some longest subsequence, and I don't assume anything about the items order:

private static <T> List<T> longestCommonSubseq(List<T> a, int indA, List<T> b, int indB){
    if (indA == a.size() || indB == b.size())
        return Collections.emptyList();

    T itemA = a.get(indA);
    T itemB = b.get(indB);

    List<T> res;
    if (itemA.equals(itemB)){
        res = new ArrayList<T>();
        res.add(itemA);
        res.addAll(longestCommonSubseq(a, indA+1, b, indB+1));
    }else{
        List<T> opt1 = longestCommonSubseq(a, indA+1, b, indB);
        List<T> opt2 = longestCommonSubseq(a, indA, b, indB+1);
        if (opt1.size()>opt2.size())
            res = opt1;
        else
            res = opt2;
    }
    return res;
}

public static <T> List<T> longestCommonSubseq(List<T> a, List<T> b){
    return longestCommonSubseq(a,0,b,0);
}

Note: For simplicity, in my solutions the lists should be random access (e.g. ArrayList).

Answer 5

Ok, I'm not making any assumptions about what you want beyond what you asked for. Below is a recursive function which finds common elements of two linked lists. It takes O(n^2) time, what that what you get with your setup.

Note that while this is tail-recursive, Java (generally) doesn't optimize that so this will blow the stack for long lists.

    import java.util.*;

    public class CommonNodeLinkedList {
        public static void main(String[] args) {
            List<Integer> list1_items = Arrays.asList(2, 5, 7, 10);
            List<Integer> list2_items = Arrays.asList(2, 4, 8, 10);

            LinkedList<Integer> list1 = new LinkedList<Integer>();
            list1.addAll(list1_items);
            LinkedList<Integer> list2 = new LinkedList<Integer>();
            list2.addAll(list2_items);

            System.out.println("List 1      : " + list1);
            System.out.println("List 2      : " + list2);
            System.out.println("Common Nodes: " + findCommonNodes(list1, list2));
        }

        public static LinkedList<Integer> findCommonNodes(LinkedList<Integer> list1,
LinkedList<Integer> list2) {
            return findCommonNodes_helper(list1, list2, new LinkedList<Integer>());
        }

        public static LinkedList<Integer> findCommonNodes_helper(LinkedList<Integer> list1,
LinkedList<Integer> list2,
LinkedList<Integer> result) {
            if (list1.isEmpty()) return result;
            Integer head = list1.pop();
            if (list2.contains(head)) {
                result.add(head);
            }
            return findCommonNodes_helper(list1, list2, result);
        }

    }

Answer 6

Hi, Please check the below link for answer: http://datastructurequestions.blogspot.com/2010/07/finding-merging-node-of-two-link-lists.html