Above answer is not correct. Its a list so you can only start from the begininning.

If its a doubly linked list, yes, you can start at the end (and should), but you cannot start "mid-list".

View Allnum of num

5 Answers

▲

2

▼

Above answer is not correct. Its a list so you can only start from the begininning.

If its a doubly linked list, yes, you can start at the end (and should), but you cannot start "mid-list".

▲

0

▼

I can think of two ways:

1) traverse from both heads, get two length: long, short

traverse again starting from Array1[long-short] and Array2[0], looking for the same pointer

O(4n) time, O(1) space

2) use a hash table holds all seen pointers. traverse from both heads

O(2n) time, O(n) space

▲

0

▼

Step 1: if the linked lists are not empty, find the length of each linked list. Since they have a common end point, we will get length of common area of the linked lists too.

Step 2: find the difference between the length of both list. Start traverse the biggest list till the difference in length between them, provided one of them is bigger than the other.

Step 3: now they are at the same remaining length. Traverse both of the together till both are pointing to the same next node.That node is the common node which is the merging point. If there is no such point, then they are not merged.

▲

0

▼

Suppose x nodes before merged node for List1, and y nodes before merged node for List 2, z shared nodes for two Lists.

List1.Length = x + z

List2.Length = y + z

Traverse List1, List2 to get their lengths.

List1.Length - List2.Length = x - y

Starting traverse at same time from (x-y+1)th nodes of List1, and head of List2 (when x>=y)

or

Starting traverse at same time from (y-x+1)th nodes of List2, and head of List1 (when x<=y)

till they point to the same node, that node is merged node. otherwise, no merged node

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

If the lists have a length value, then you should be able to do this pretty simply.

If two lists merge, then they have the same terminal node. That means that from the merge node to the end they have the same length. So if you subtract the smaller lists length from the larger you end up with a great starting point to begin searching. you then increment down the lists from that point on to find the node where both lists meet.