Find common nodes from two linked lists using recursion

Question

I need to write a method that returns a linked list with all nodes that are common to two linked lists using recursion, without loops.

For instance,

the first list is 2 → 5 → 7 → 10

the second list is 2 → 4 → 8 → 10

the list to be returned will be 2 → 10

I can’t do anything with this .. What I was thinking about is checking each value of the first list with each value of the second list recursively, but the second list will then be cut into one node each time, and I cannot compare the next value in the first list with the second list. Hope this makes sense ...

Can anyone help?

Answer 1

This question only has weight in it if the values ​​in each list are sorted. If this happens, then it 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 lengths L1 and L2 , this will combine them into O(L1 + L2) . He does this without destruction, creating new nodes for duplicates. You can easily change it to “steal” from one of the lists if you want.

Answer 2

This issue is subject to restrictions.

The simplest, most naive solution is if you have two elements of size n , you iterate over one list and compare it with all the elements in the second list.

Solution: O (n ² )

But of course you can do much better.

Now, if you have a HashSet data structure available (or another close to O (1)), then this is what you can do:

Iterate over a single list. Add each item to the set. Go to the second list. If the item is in a set, add it to the list of results.

Solution: O (n)

Answer 3

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

http://www.geeksforgeeks.org/intersection-of-two-sorted-linked-lists/ look at the third 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 4

If you don't need duplicates using the built-in keepAll () method, this is a simple 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 5

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

In my recursive solution, I assume that we are looking for some longest subsequence , and I do not assume anything about the order of the elements:

 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 decisions, lists should be random access (e.g. ArrayList).

Answer 6

Well, I make no assumptions about what you want, other than what you requested. Below is a recursive function that finds common elements of two linked lists. It takes the O (n ^ 2) time that you get with your setup.

Note that although this is tail recursion, Java (usually) does not optimize this, so this will remove 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 7

There are two lists of links:

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

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

Then we need to figure out the node merge.

Algo:

• Calculate the length of the first list of links, say, this is "len1".
• Calculate the length of the second list of links, say, this is "len2".
• Learn the great lengths from len1 and len2. in this example len1> len2.
• Find out the positive difference between len1 and len2, in this example | len1 - len2 |
• Now take 1 pointer (ptr1) in the list of large links and place it on | len1 - len2 | from the very beginning.
• Take 1 pointer (ptr2) and place it at the top of the link list 2.
• increment both pointers one by one and check them if they occur then this is the merge point of the two link lists.

Algo with this example: 1. len1 = 8 2. len2 = 7 3. len1> len2 4. | len1 - len2 | = 1 5. ptr1 = 2 node of the first list of links 6. ptr2 = 1 node of the second list of links 7. in link list1, 3rd → next and c → next in the list of links2 will point to the same node, which is the 4th node, therefore, it is a merge node.