java - How can a singly-linked list have two heads, and what does it mean to find their "common node"? -

the javadocs methods below includes:

the singly linked list in problem has 2 heads, n1 , n2, merge @ common node. return first common node accessible both n1 , n2. must run in o(n) time.

i don't understand purpose of code. how can singly-linked list have 2 heads? common list (or common node), , why returned?

could provide examples of input list or lists, , or after findcommonlist method returns?

the code is:

public static<e> listnode<e> findcommonlist(listnode<e> n1, listnode<e> n2) { int length1 = getlength(n1); int length2 = getlength(n2); if (length1 > length2)     n1 = advance(n1, length1 - length2); else     n2 = advance(n2, length2 - length1); while (n1 != n2) {     n1 = n1.next;     n2 = n2.next; } return n1; }  private static<e> listnode<e> advance(listnode<e> n, int k) { while (k > 0) { n = n.next; k--; } return n;  }  private static<e> int getlength(listnode<e> n) { int total = 0; while (n != null) {     total++;     n = n.next; } return total; } 

i can't see code listnode, i'm guessing it's pretty typical single-linked list, reference data of type e , reference next listnode, called next. last listnode point next null. ignoring references data, typical list this:

lna→lnb→lnc→…→lnz→null 

one of (many) problems kind of structure no 1 list "owns" of these listnode instances, multiple lists can tangled up:

ln0→ln1→ln2↘             lnq→lnr→…→lnz→null lna→lnb→lnc↗ 

the findcommonlist method takes 2 listnode references, n1 , n2, , goes searching first node "to right" have in common, marks start of common tail.

what n1 , n2 share common tail depends on start. putting them in obvious places:

n1 ↓ ln0→ln1→ln2↘             lnq→lnr→…→lnz→null lna→lnb→lnc↗ ↑ n2 

...would return lnq start of common tail. (if n2 had instead started @ lnz, result couldn't have included lnq --- it's no longer in 1 of lists, , not common them both.)

the javadoc implies code works in situation 1 above, handles few related cases may @ first appear different, when n1 , n2 point different elements of same list:

n1 ↓ ln0→ln1→ln2→ln3→ln4→…→null             ↑             n2 

or when point 2 unrelated lists... since lists end reference null, 2 "completely independent" lists return null start of (zero-length) common tail:

n1 ↓ ln0→ln1→ln2→ln3→ln4↘                     null         lna→lnb→lnc↗         ↑         n2 

how findcommonlist works

the first thing findcommonlist find how "far" n1 , n2 end of respective lists (how many elements separate each null).

in example, n1 "2 farther" n2:

n1 ↓ ln0→ln1→ln2→ln3→ln4↘                     lnq→…→lnz→null         lna→lnb→lnc↗         ↑         n2 

then, advances farther of 2 references same distance null other. elements skipped on can't conceivably part of common tail, because there's no way common tail can longer 1 of input lists.

after advancing n1:

        n1         ↓ ln0→ln1→ln2→ln3→ln4↘                     lnq→…→lnz→null         lna→lnb→lnc↗         ↑         n2 

now we've reached while loop, can reworded as:

start: if n1 , n2 point same listnode:     return listnode otherwise:     advance n1 , n2 each 1 hop right go "start" 

this bit said above "goes searching first node 'to right' have in common". when it's done, n1 , n2 both point @ same listnode, lnq, returned:

                    n1                     ↓ ln0→ln1→ln2→ln3→ln4↘                     lnq→…→lnz→null         lna→lnb→lnc↗                     ↑                     n2 

note works in other cases outlined above, too.

if n1 , n2 refer 2 independent lists:

n1 ↓ ln0→ln1→ln2→ln3→ln4↘                     null         lna→lnb→lnc↗         ↑         n2 

first, farther reference advance:

        n1         ↓ ln0→ln1→ln2→ln3→ln4↘                     null         lna→lnb→lnc↗         ↑         n2 

and while loop advance both references in lockstep until reach "node" 2 lists have in common, null:

                    n1                     ↓ ln0→ln1→ln2→ln3→ln4↘                     null         lna→lnb→lnc↗                     ↑                     n2 

if n1 , n2 point same list, it's easier:

n1 ↓ ln0→ln1→ln2→ln3→ln4→…→null             ↑             n2 

findcommonlist start advancing far reference, same before:

            n1             ↓ ln0→ln1→ln2→ln3→ln4→…→null             ↑             n2 

...and it's done! findcommonlist return reference ln3, without ever executing body of while loop.

finally, if n1 , n2 start pointing same listnode:

n1 ↓ ln0→ln1→ln2→ln3→ln4→…→null ↑ n2 

...the adjustment step nothing ("advance 0 hops"), , ln0 returned, again without executing body of while loop.