The problem is the same as my title. I am now studying the data structure and struggling with the problem. the LinkedList now has a dummy head and it is impossible to make another global variable.

public int numItems() {
 just here is the all I can modify.
}

I think that to solve this problem using recursion, there must be an argument for the method. But as I am a Noob coder, I am not sure about my opinion.

I tried the first method with no arguments and it calls another method with arguments like

public int numItems() { 
  return numItems(head);
}

public int numItems(Node node) {
  if(node.next == null) {
    return 0;
  } else {
    return 1   numItems(node.next); 
  }
} 

using Java's method of overloading. but this too is not a proper answer to this question. So, if you have any idea that can code the counting of the number of the elements in LinkedList using recursion, please let me know... or if it is impossible also please tell me that it is not possible.

CodePudding user response：

You can solve by accumulating the count on each node travel.

public int numItmes(Node node, int accumulator){
    if(node == null){
        return accumulator; 
    }

    return numItmes(node.next, 1   accumulator)
}

numItmes(node, 0);

CodePudding user response：

You can recursively count the number of elements in your linked list by starting at your first actual node and not in a "hypothetical" head.

Your end-result should look something like this:

public int numItems() {
    return numItems(head.next); // start at the first actual node
}

private int numItems(Node node) {
    if (node == null) {
        return 0;
    }
    return 1   numItems(node.next);
}

And you don't need any method overloading for this problem .

CodePudding user response：

There is a number of clarifications to ask here:

• Is numItems method of LinkedList?
• It is not the best practice, but is it okay or is it possible in your case to mutate the dummy head?

public int numItems() {
    if (null == this.dummyHead) {
        return 0;
    }
    this.dummyHead = this.dummyHead.next;
    return 1   this.numItems();
}

Note: It is not a production like practice, but solves the case within your limitations.

Update: there is possibly off by one if we don't want dummyHead to be counted in. In that case if we are guaranteed to have the dummyHead all the time, then instead of 0 in the null check we should return -1 instead to be precise.