Problem
Given the head pointers (head1 and head2) of two linked lists, find the intersection node of the two lists.
For the above image, program needs to output: 4 as the intersection point.
Naive Approach
Run two for loops: outer loop from 0 to head1.length() and inner loop from 0 to head2.length(). Match each node of list1 with each node of list2. If there’s a match return node->value.
Pseudocode
Solve (head1, head2) 1. node1 = head1, node2 = head2 2. length1 = head1.size(), length2 = head2.size() 3. for i=0 to length1: 4. for j=0 to length2: 5. if (node1 == node2) then: 6. return node1->value 7. node2 = node2->next 8. node1 = node1->next 9. return null
Time Complexity: O(M*N) [where, M and N be the length of two linked lists respectively]
Auxiliary Space: O(1)
Optimised Approach
Let length1 will be the length of list1 and length2 will be the length of list2. Now assuming length1 > length2. Traverse list1 from head (0) to the difference of the two lists’ length (d = length1 – length2). Now we could traverse both the lists simultaneously to meet the intersection point, since the extra nodes of list1 have already been traversed.
Pseudocode
Solve (head1, head2) 1. node1 = head1, node2 = head2 2. length1 = head1.size(), length2 = head2.size() 3. d = length1 - length2 3. if length1 < length2 then: 4. node1 = head2 5. node2 = head1 6. d = length2 - length1 7. for i=0 to d: 8. node1 = node1-next 9. while (node1 != node2): 10. node1 = node1->next 11. node2 = node2->next 12. return node1
Time Complexity: O(M + N)
Auxiliary Space: O(1)
Code Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | //// main.cpp// Intersection Point//// Created by Himanshu on 03/10/21.//#include <iostream>using namespace std;struct node { int info = 0; struct node *next;};typedef struct node Node;node* newNode(int data) { node* Node = new node(); Node->info = data; Node->next = NULL; return(Node);}void printLinkedList (Node* head) { Node *x = head; while (x != NULL) { cout<<(x->info)<<" "; x = x->next; } cout<<endl;}Node* insertNode (Node *head, Node* x) { Node *node = head; while (node->next != NULL) { node = node->next; } x->next = NULL; node->next = x; return head;}Node* searchNode (Node *head, int k) { Node* x = head; while (x != NULL && x->info != k) { x = x->next; } if (x != NULL && x->info == k) { return x; } else { return NULL; }}int findListLength (Node *head) { int len = 0; Node *node = head; while (node != NULL) { len++; node = node->next; } return len;}Node* solve (Node *head1, Node *head2) { Node *node1 = head1, *node2 = head2; int len1 = findListLength(head1), len2 = findListLength(head2); int diff = len1 - len2; if (len1 < len2) { node1 = head2; node2 = head1; diff = len2 - len1; } for (int i=0; i<diff; i++) { node1 = node1->next; } while (node1 != node2) { node1 = node1->next; node2 = node2->next; } return node1;}int main() { Node *head1 = newNode(1); Node *head2 = newNode(9); head1 = insertNode (head1, newNode(2)); head1 = insertNode (head1, newNode(3)); head1 = insertNode (head1, newNode(4)); head1 = insertNode (head1, newNode(8)); head2 = insertNode (head2, newNode(5)); head2 = insertNode (head2, newNode(7)); Node *x = searchNode(head2, 7); x->next = searchNode(head1, 4); cout<<"Linked List 1:"<<endl; printLinkedList(head1); cout<<"Linked List 2:"<<endl; printLinkedList(head2); x = solve(head1, head2); if (x) { cout<<"Intersection point is: "<<(x->info)<<endl; } else { cout<<"No intersection point found"<<endl; } return 0;} |
Output
Linked List 1: 1 2 3 4 8 Linked List 2: 9 5 7 4 8 Intersection point is: 4
Here’s a working example: Intersection point of two linked lists