Determine common and distinct nodes between two sorted linked lists recursively

taurus05 0
Viewed 44

Consider following example : l1, l2, common, unique are 4 linked lists. Nodes in l1 and l2 are in sorted order. common and unique and empty linked lists.
l1 = 1->3->5->8
l2 = 3->4->8->9
common = null
unique = null

Using iterative method, I figured out that I can easily find common and unique elements as follows:

  1. Traverse l1 and l2
  2. If l1->data < l2->data, add a new node with l1->data to unique and increment pointer for l1
  3. If l1->data > l2->data, add a new node with l2->data to unique and increment pointer for l2
  4. If l1->data == l2->data, add a new node with l2->data to common and increment pointers for both l1 and l2.

I can't figure out the recursive approach for this problem.

Update:
Both the linked lists can be thought of as set of elements sorted in ascending order. A number can occur at most twice. (Either in both of them, or in exactly one of them, or none of them).

linked-list data-structures recursion algorithm c++
1 Answers

Here is a simple, recursive algorithm based on the description that you've added:

function get_unique(l1, l2, unique, common):
    if not l1:
        unique -> next = l2
        return
    else if not l2:
        unique -> next = l1
        return
    else if l1 == l2:
        common -> next = new node(with value = l1.value)
        common = common -> next
        l1 = l1 -> next
        l2 = l2 -> next
    else:
        if l1.val < l2.val:
            unique -> next = new node(with value = l1.value)
            l1 = l1.next
        else:
            unique -> next = new node(with value = l2.value)
            l2 = l2.next
        unique = unique.next
    get_unique(l1, l2, unique, common)
Abhinav Mathur0
Related