Printing heads of stand-alone lists Please review my code to help improve its quality.

public void printHeadOfNonIntersectingLinkedList(List&lt;Standalone&gt; listStandalones) {
    final Map&lt;Node, Node&gt; tailHeads = new HashMap&lt;Node, Node&gt;();

    for (Standalone ll : listStandalones) {
        Node temp = ll.first;
        while (temp.next != null) {
            temp = temp.next;
        }
        if (tailHeads.containsKey(temp)) {
            tailHeads.put(temp, null);
        } else {
            tailHeads.put(temp, ll.first);
        }
    }

    for (Entry&lt;Node, Node&gt; entry : tailHeads.entrySet()) {
        if (entry.getValue() != null) {
            System.out.println(entry.getValue().element);
        }
    }
}
First of all, you have provided very little context for your code. Therefore, my criticism may not be valid in the context of your full program.

Second, you have not a single comment in your code. One can argue that code does not need comments once it is self-documenting. But your code does not achieve that.




Your method does not use any variables defined outside of your function. This shows that


… it should be marked as static – it clearly does not operate on an instance of the class where this function is defined.
… Static methods can be an indication that your code is not object oriented. It may need to be redesigned.
… You do operate on an object: List&lt;Standalone&gt;. Maybe that should be a class of its own, and this method be an instance method over there.

printHeadOfNonIntersectingLinkedList is far to long as a name. I know that Java code has the tendency to prefer such long names, but you are not doing anyone a favour with that. In addition:


The name does not match the behaviour of the method. Doesn't it print the heads belonging to unique tails of linked lists? The lists itself may intersect.
The name tells us that this method is doing too many unrelated things. It needs to be refactored. The different parts are: finding the tails of all lists, deduplicating the nodes, and printing them out.

List&lt;Standalone&gt; – why not Iterable&lt;Standalone&gt;? There is no need to be extra specific, and all we do is call an implicit .iterator() on it.
+1 for using final, although you could designate the loop variables as final as well.
tailHeads is a confusing name. seenTails might be better.
ll is a bad name. Avoid short names, especially abbreviations. Exceptions to this rule are integer loop variables (i, j, …) and domain-specific code where not using common abbreviations would be more confusing. Examples would be highly mathematical (e.g. cryptographic) code. In this case, linkedList could be a better choice.
Finding the last element in a list is an implementation detail, and should be encapsulated in the Standalone class – it doesn't seem to be very “standalone” after all. If you didn't write that class: Subclass it and implement these helpers there.

final Node tail = linkedList.tail();

The next part makes a lot of sense, and can't be written any better. But it is crucial to use comments to tell a reader what you are doing here:

// If that tail is already known, mark it as seen,
// but unwanted with a null.
if (seenTails.containsKey(tail)) {
    seenTails.put(tail, null);
} ...

Using .entrySet() is a bit akward, considering that you are only interested in the values. Why not for (final Node head : seenTails.values()) { ... }?
Let another method do the printing – just return a collection or iterator of the values of each head, and be done with it.




Here is my take on making that code more self-documenting, heeding some of my above criticism. Untested.

class Standalone {
  private Node head;  // proper encapsulation
  private NodeValue element;
  ...

  public Node head() {
    return head;
  }

  // you might want to cache this
  public Node tail() {
    // handle zero-length lists
    if (head == null)
      return null;

    // find and return last element
    Node pointer = head;
    while (pointer.next != null)
      pointer = pointer.next;
    return pointer;
  }

  public NodeValue element() {
    return element;
  }

  public static Iterable&lt;Standalone&gt; withUniqueTails(Iterable&lt;Standalone&gt; standaloneCollection) {
    final HashMap&lt;Node, Standalone&gt; uniqueTails = new HashMap&lt;Node, Node&gt;();
    final HashSet&lt;Node&gt;             duplicates  = new HashSet&lt;Node&gt;();

    for (final Standalone list : standaloneCollection) {
      final Node tail = list.tail();
      if (duplicates.contains(tail)
        continue;
      if (uniqueTails.containsKey(tail)) {
        uniqueTails.remove(tail);
        duplicates.add(tail);
      } else {
        uniqueTails.put(tail, list)
      }
    }

    return uniqueTails.values();
  }
}


Calling code could be like

for(final Standalone standalone : Standalone.withUniqueTails(someStandalones)) {
  System.out.println(standalone.head().element());
}


Do you notice something? The method is actually just a filter that skips over some values (we could lift this kind of code to all kinds of iterator transformation strategies). And this is the only thing my version of that method does. If you need a wrapper that extracts the head values, you can write it, without having to concern yourself with filtering out unwanted values.

If you need a helper that prints out each element in some iterable one line at a time, you can write that too. Make it private to reduce the shame.

private static &lt;T&gt; void printCollection(OutputStream stream, Iterable&lt;T&gt; collection) {
  for(final T item : collection)
    stream.println(item);
}




Update:

Programming is a game of tradeoffs. We can optimize along axes of readability, theoretical elegance, memory usage, speed, and sometimes other resources like network requests. If in doubt, it is advisable to optimize for readability.

In my suggested rewrite, I introduced duplicates mostly in order to make the code more self-documenting: If a duplicate node is detected, then it is literally removed from the unique nodes, and added to the duplicates. I avoided the (otherwise completely legitimate) use of null as a special value.  This intends to make the code simpler to understand.

We can estimate the performance characteristics of introducing another data structure.

Space

First, memory usage. The worst case scenario is that our input data is unique throughout the first half of the input, then repeats one or more times: A, B, C, ..., Z, A, B, C, ..., Z, where the number of elements n is chosen in a way that it forces a resizing of the hash table.

After that code has been filtered, we find zero elements in uniqueTails, because all were duplicates. That data structure has capacity for (n-1)*2 elements (hash table size is doubled when a certain load factor is reached). We have n elements in duplicates, which also has size for (n-1)*2 elements. Thus in the worst case, we have allocated 2× as much memory as neccessary. But if one of those elements is unique, we can avoid the table size doubling in duplicates, thus using only 1.5× as much memory. If the duplicates are adjacent (A, A, B, B), then the uniqeTails never grow (best case scenario).

Depending on the exact numbers of unique duplicate elements, the acceptable load factor, and the longest streak of unique elements, we can get anything from 1× to 2× the memory usage (plus overhead), but will rather stay at the lower end of that range. I consider this acceptable for most scenarios.

Time

The addition of another data structure comes at the cost of more recalculations of the hash. The hash code must be calculated for contains, containsKey, remove, add, put. Per element, a 1–4 calculations can occur in my code. Your original code does this in always exactly 2 calculations. Only when a key occurs more than eight times, less recalculations occur.

Summary: My code will quite certainly perform worse – but it was never tuned for performance. By all means, use tricks like null pointers as special values to express an extra level of information. But if you do so, document it with a comment (you'll note that I did exactly that in the main part of my review).