Counting number of nodes between two nodes

Focusing directly on the countNodesBetweenTwoNodes

  private int countNodesBetweenTwoNodes(Node firstNode, Node secondNode) {
    int count = 0;

    while(firstNode.next != secondNode) {
        count++;
        firstNode = firstNode.next;
    }

    return count;
  }

The method name is way too long... that's an AppleScript name! The arguments in a Java method count as part of the signature, so, your method is really calling it countNodesBetweenTwoNodes Node Node... it is quite sufficient to call it countNodesBetween(Node, Node)...

Then, the parameters are Nodes, so there is no need to call them firstNode and secondNode, first and second would be fine.

Alright, so, now we have the method:

  private int countNodesBetween(Node first, Node second) {
    int count = 0;

    while(first.next != second) {
        count++;
        first = first.next;
    }

    return count;
  }

Now, about the real issues, what if first == second? Then the result should be 0, but, in your case, it is size where `size is the number of members in the list.

  private int countNodesBetween(Node first, Node second) {
    int count = 0;

    while(first != second) {
        count++;
        first = first.next;
    }

    return count;
  }

This changes the value that you are returning though.... but... what was the requirement?

Was the requirement to get the number of steps to go from the first to the second, or the number of in-between nodes you have to visit?

If it was the number of nodes you have to visit, then you have two places where the result is 0, when first == second, and also first.next == second...

In a general sense, I have never encountered a reason why there has to be a full loop-count when the first==second

Finally, what if you are going the long way around? For example, what if someone does this?

countNodesBetween(mynode.next, mynode);
countNodesBetween(mynode, mynode.next);

Shouldn't the answer there be 1 for both situations (unless mynode.next == mynode)?

To my mind, this method should look like:

  private int countNodesBetween(final Node first, final Node second) {
    int count = 0;
    int size = 0;
    Node tmp = first;
    while(tmp != second) {
        count++;
        tmp = tmp.next;
        if (tmp == first) {
            throw new IllegalArgumentExcption("First and second nodes are not in the same list.");
        }
    }
    if (count <= 1) {
        return count;
    }
    int size = count;
    while (tmp != second) {
        size++;
        tmp = tmp.next;
    }
    int back = count - size;
    return -back < count ? back : count;
  }

This code loops all the way around the loop, and it returns the distance between the nodes, where 'between' is defined as 'how many times do you have to move to get from the first to the second.

It returns a negative number if the shortest distance is to go backward through the loop... or, put another way, the number of steps forward from the second node to the first.

If that information is not relevant to you, you can stick with the simpler:

  private int countNodesBetween(final Node first, final Node second) {
    int count = 0;
    int size = 0;
    Node tmp = first;
    while(tmp != second) {
        count++;
        tmp = tmp.next;
        if (tmp == first) {
            throw new IllegalArgumentExcption("First and second nodes are not in the same list.");
        }
    }
    return count;
  }