Intersection of two Sorted Linked Lists | GeeksforGeeks

Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.

Method 2 (Using Local References) 
This solution is structurally very similar to the above, but it avoids using a dummy node Instead, it maintains a struct node** pointer, lastPtrRef, that always points to the last pointer of the result list. This solves the same case that the dummy node did — dealing with the result list when it is empty. If you are trying to build up a list at its tail, either the dummy node or the struct node** “reference” strategy can be used

struct node* sortedIntersect(struct node* a, struct node* b)

{

  struct node* result = NULL;

  struct node** lastPtrRef = &result;

  /* Advance comparing the first nodes in both lists.

    When one or the other list runs out, we're done. */

  while (a!=NULL && b!=NULL)

  {

    if (a->data == b->data)

    {

      /* found a node for the intersection */

      push(lastPtrRef, a->data);

      lastPtrRef = &((*lastPtrRef)->next);

      a = a->next;

      b = b->next;

    }

    else if (a->data < b->data)

      a=a->next;       /* advance the smaller list */   

    else   

      b=b->next;   

  }

  return(result);

}

Method 3 (Recursive)

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

Read full article from Intersection of two Sorted Linked Lists | GeeksforGeeks