(E-Mail Removed) wrote:

> Richard Heathfield <(E-Mail Removed)> wrote:

> > ... Consider these linked lists:

>

> > listA: A -- B -- C -- D

> > * * * * * * * * * * * *\

> > * * * * * * * * * * * * E -- F -- G

> > * * * * * * * * * * * */

> > listB: * * * * * H -- I
<snip>

> > I believe this has to be done in two nested loops (or at

> > least, "as if" it were two nested loops! - i.e.

> > O(listAnodecount * listBnodecount)), but I'd

> > be delighted to be proved wrong.

>

> How about - you measure the length of the lists, subtract

> one from the other, and step that number of steps into the

> longer list. Now step through each list simultaneously,

> looking for a match.
More formally...

Declare the following variables

LA := length of list A

LB := length of list B

LB' := length of list B if list A is reversed

DA := number of leading nodes distinct to A

DB := number of leading nodes distinct to B

CAB := number of nodes common to A and B

From observation, we have...

LA = DA + CAB

LB = DB + CAB

LB' = DB + DA + 1

Rewritten as...

DA + CAB = LA

DB + CAB = LB

DA + DB = LB' - 1

Which is solved by...

CAB := (LB - LB' + LA + 1)/2

DA := LA - CAB

DB := LB - CAB

The algorithm (including restoration of A from G) is left

as an exercise, but it should be clear that since reverse

and length count are O(N), and we perform a fixed number

of steps of each, the algorithm is O(N + M).

Or I may have forgotten to carry 1 and I'm talking *******s.

--

Peter