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

If the linked list is already sorted, than you can apply recursion very effectively this is from GeeksforGeeks

http://www.geeksforgeeks.org/intersection-of-two-sorted-linked-lists/ look at the 3rd option.

struct node *sortedIntersect(struct node *a, struct node *b)
{
    /* base case */
    if (a == NULL || b == NULL)
        return NULL;

    /* If both lists are non-empty */

    /* advance the smaller list and call recursively */
    if (a->data < b->data)
        return sortedIntersect(a->next, b);

    if (a->data > b->data)
        return sortedIntersect(a, b->next);

    // Below lines are executed only when a->data == b->data
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = a->data;

    /* advance both lists and call recursively */
    temp->next = sortedIntersect(a->next, b->next);
    return temp;
}

Answer 2

There are two link list like below:

1--->2--->3--->4--->5--->6--->7--->8

a--->b--->c--->5--->6--->7--->8

Then we need to find out the merging node.

Algo:

1. Calculate the length of first Link List, lets say it is "len1".
2. Calculate the length of second Link List, lets say it is "len2".
3. Find out the greater length out of len1 and len2. in the given example len1 > len2.
4. Find out the positive difference of len1 and len2, in given example |len1 - len2|
5. Now take 1 pointer (ptr1) on the big link list and place it on the |len1 - len2| position from the start.
6. Take 1 pointer (ptr2), and put it on the start of Link list 2.
7. increase both pointer one by one, and check them, if they meet then that is the merging point of two link lists.

Algo with Given example: 1. len1 = 8 2. len2 = 7 3. len1 > len2 4. | len1 - len2 | = 1 5. ptr1 = 2 node of first link list 6. ptr2 = 1 node of second link list 7. in link list1, 3rd-->next and c-->next in link list2 will be pointing to same node, which is 4th node, hence it is the merging node.

Answer 3

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

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 6

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 7

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)