Coderust: Hacking the Coding Interview/

...

/

Intersection Point of Two Lists

Intersection Point of Two Lists

Given the head of two linked lists, find out if they intersect and return the point of intersection.

We'll cover the following...

Statement

Given the head nodes of two linked lists, return the node at which the two lists intersect. We will return null if we do not find any intersection between the two linked lists.

Note: The input linked list will not have cycles in it.

Example

In the below example, lists do not intersect each other.

g head1 head1 a 29 head1->a head2 head2 NULL NULL b 23 a->b c 82 b->c d 11 c->d e 12 d->e f 27 e->f f->NULL a2 13 head2->a2 NULL2 NULL b2 4 a2->b2 b2->NULL2

After adding nodes 12 and 27 in the linked list head2, the list now has the same nodes as the linked list head1.

g head1 head1 a 29 head1->a head2 head2 NULL NULL b 23 a->b c 82 b->c d 11 c->d e 12 d->e f 27 e->f f->NULL a2 13 head2->a2 NULL2 NULL b2 4 a2->b2 c2 12 b2->c2 d2 27 c2->d2 d2->NULL2

However, in the below example, both lists intersect at the node with data 12. The node 4 in linked list head2 points to node 12 and the node 11 in linked list head1 points to node 12 (with the same address).

g head1 head1 a 29 head1->a head2 head2 NULL NULL b 23 a->b c 82 b->c d 11 c->d e 12 d->e f 27 e->f f->NULL a2 13 head2->a2 b2 4 a2->b2 b2->e

Sample input

[13, 4, 12, 27]
[29, 23, 82, 11, 12, 27]

Expected output

12

Try it yourself

The linked lists have to physically intersect. This means that their addresses need to be the same. If two nodes have the same data but their addresses are not the same, the lists won’t intersect and the function should return null.

main.cpp
LinkedList.cpp
LinkedListNode.cpp
#include "LinkedList.cpp"
using namespace std;
LinkedListNode* Intersect(LinkedListNode* head1, LinkedListNode* head2) {
	//TODO: Write - Your - Code
	return head1;
}

Solution 1

Firstly, we’ll find the lengths of both L1L1 and ...