4Methods:Intersection of 2 sorted LL

 Method1: using dummy node

method2: using local references

method3: a recursive approach

using dummy node: put a dummy temp node at the start of the result list. Pointer tail will always point to the last node in the result list, so new nodes can be added easily. 

dummy node gives the tail a special memory to point to. This dummy node is efficient as it is temporary, and it is allocated in the stack. 

The loop proceeds removing one node from either a or b and adding it to the tail. 

when the given lists are traversed, the result is in dummy. next as the values are allocated from the next node of the dummy. 

If both the elements are equal then remove both and insert the element to the tail. else remove the smaller element among both the lists.

Code:

void push(node** head_ref, int new_data)

{

  node dummy; node* tail= &dummy;

  dummy.next= NULL; 

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

{

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

{

push((&tail->next),a->data);

tail=tail->next; a=a->next;

b=b->next;

} //if ends

//advance the small linked list

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

a=a->next;

else b=b->next;

} \\while ends

return (dummy.next);

} //function ends

void push(node** head_ref, int new_data) {}

void printlist(node* head) {}

int main() {}

TC- O(M+N)

Method2: using local references

Using local reference is structurally very similar to the dummy node method.  But we do not use a dummy node in this method. 

Instead, it maintains a struct node** pointer, lastPtrRef that always points to the last pointer of the result list. 

This solves the case that the dummy node did.  If we want to make the list at the tail node, either dummy method or struct node** reference method can be used. 

struct node{} 

void push(struct node** head_ref, int new_data) {} 

void node* sortedintersect(struct node* a, struct node* b)

{

struct node* result= NULL; //took a pointer name result

struct node** lastPtrRef = &result;

//advance comparing first nodes in both lists. 

//when 1 lists ends , we are done

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

{

if(a->data==b->data) //got matching data

{

push(lastPtrRef, a->data);

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

a=a->next; b=b->next;

} //ifends

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

a=a->next; //advance th smaller list

esle b=b->next;

} //while ends

return (reuslt);

}

void push(struct node** head_ref, int new_data) {}

void printlist(struct node* head)

int main() {}

Method3: Recursive sol