Method 1 (Brute Force)
Using 2 for loops. Outer loop will be for each node of the 1st list and inner loop will be for 2nd list. In the inner loop, check if any of nodes of 2nd list is same as the current node of first linked list. Time complexity of this method will be O(lm) where l and m are the number of nodes in two lists.Find the length of both the linked list
Find the difference in length(d)
For the longer LL, traverse d node and check the addresses with another LL
Method 2
Find the length of both the linked list
Find the difference in length(d)
For the longer LL, traverse d node and check the addresses with another LL
/* Link list node */ struct node { int data; struct node* next; }; int getCount(struct node* head); int getIntesectionNode(int d, struct node* head1, struct node* head2); /* function to get the intersection point of two linked lists head1 and head2 */ int getIntesectionNode(struct node* head1, struct node* head2) { int c1 = getCount(head1); int c2 = getCount(head2); int d; d = abs( c1 - c2); if(c1 > c2) { return getIntesectionNode(d, head1, head2); } else { return getIntesectionNode(d, head2, head1); } } /* function to get the intersection point of two linked lists*/ int getIntesectionNode(int d, struct node* head1, struct node* head2) { int i; struct node* current1 = head1; struct node* current2 = head2; for(i = 0; i < d; i++) { if(current1 == NULL) { return -1; } current1 = current1->next; } while(current1 != NULL && current2 != NULL) { // we are comparing the addresses not data if(current1 == current2) return current1->data; current1= current1->next; current2= current2->next; } return -1; } /* Takes head pointer of the linked list and returns the count of nodes in the list */ int getCount(struct node* head) { struct node* current = head; int count = 0; while (current != NULL) { count++; current = current->next; } return count; }
Complexity: O(m+n)
Space : O(1)
can any one explain that approach..
Ideas followed here is that if the linked list are of same length, finding intersecting node is O(n), because we can check one to one node in both list, calculating length is part of doing that.
Though the above program should handle the case when both list are of same length.