Check if two linked lists merge. If so, where?

algorithm linked-list data-structures
rplusg picture rplusg · Oct 20, 2009 · Viewed 43.3k times · Source

This question may be old, but I couldn't think of an answer.

Say, there are two lists of different lengths, merging at a point; how do we know where the merging point is?

Conditions:

  1. We don't know the length
  2. We should parse each list only once.

Example of two merged linked lists.

Answer

Pavel Radzivilovsky picture Pavel Radzivilovsky · Feb 19, 2013

The following is by far the greatest of all I have seen - O(N), no counters. I got it during an interview to a candidate S.N. at VisionMap.

Make an interating pointer like this: it goes forward every time till the end, and then jumps to the beginning of the opposite list, and so on. Create two of these, pointing to two heads. Advance each of the pointers by 1 every time, until they meet. This will happen after either one or two passes.

I still use this question in the interviews - but to see how long it takes someone to understand why this solution works.

Related questions

How to reverse a singly linked list using only two pointers?

I wonder if there exists some logic to reverse a singly-linked list using only two pointers. The following is used to reverse the single linked list using three pointers namely p, q, r: struct node { int data; struct node *link; }; …

Read More
How to detect a loop in a linked list?

Say you have a linked list structure in Java. It's made up of Nodes: class Node { Node next; // some user data } and each Node points to the next node, except for the last Node, which has null for next. Say …

Read More
How to find nth element from the end of a singly linked list?

The following function is trying to find the nth to last element of a singly linked list. For example: If the elements are 8->10->5->7->2->1->5->4->10-&…

Read More