Intersection of two linked lists
Given two sorted linked lists, find intersection of two linked lists. For example:
List 1 : 1->2->3->4->5->NULL List 2 : 2->3->5->6->NULL Output : 2->3->5->NULL
List 1 : 1->2->3->5->NULL List 2 : 2->5->NULL Output : 2->5->NULL
Before going into details about solution of intersection of two linked lists problem, let’s understand how a node can be added at the end of a list efficiently. One way to add node at end is to traverse entire linked list and add node there.
Other way is use pointer reference of last node every time a new node is added. For this technique, we use a local “reference pointer” which always points to the last pointer in the list instead of to the last node. This pointer will be used for all additions in the list. The reference pointer starts off pointing to the head pointer. Later, it points to the next field inside the last node in the list. Let’s see code and understand how it works.
Push(lastPtrRef, num); adds a new node at the last pointer. The new node becomes the last node in the list.
lastPtrRef= &((*lastPtrRef)->next); Advance the lastPtrRef to now point to the next field inside new last node — that next field is now the last pointer in the list. Below figure explains the working of above code.
Find intersection of two linked lists using lastPtrRef
Since we have already seen how can we add a node at the end of a list using last pointer reference, it is very easy from here on. All we need to do is to traverse two linked lists and if nodes are same, add one of them to new list. Below code is self explanatory.
Complexity of algorithm to find intersection of two linked list using last pointer reference is O(m+n) where m and n are length of two list.
Find intersection of two linked lists recursively
If you know how to merge two sorted linked list, this solution is extension of that. If you don’t please refer : Merge two linked list.
All change that needs to be done is whenever two nodes are same, create new node and add it to new list. Algorithm is below
1. Start with head of each list 2. Compare data of nodes of two list 2.a if data in node of first list smaller, advance first list ptr. 2.b else advance second list ptr. 2.c if data is equal, allocate new node with data. 3. Point next of new node to result of intersection function. temp->next = intersection(a->next, b->next) Advance both pointers. 4. Return new node created in step 3.
Complexity of recursive method to find intersection of two linked list is again O(m+n). However, there is implicit space complexity of O(max(m,n)) due to recursion.
Please share your thoughts, any suggestion or if you find something wrong, please leave a comment. Sharing is caring. If you are interested in contributing to website or have an interview experience to share, please contact us.