Recursive linked lists in Java

Question

I am working on an assignment that forces me to write a java program to print in the reverse order of the data contained in a linked list using recursion. So far this is what I have, it works, but only on the last item in the IE list. it stops when it prints the last item.

public String reverse(IntNode head){
        String result = "";
        if(head.getLink() == null){
            result += head.getData();
            return result;
        }

        else if(head.getLink().getLink() == null){
            result += head.getLink().getData();
            head.removeNodeAfter();
            return result;
        }

        else{
            return reverse(head.getLink());
        }
    }

How do I get it to continue browsing the list behind the recursive tree?

Answer 1

As others have pointed out, your decision is more complicated than it should be.

First, note that you do not need (and probably do not want to) remove any items from the list in order to go through it.

-, , , node , , ( , ). .

public String reverse(IntNode head) {
    if (head == null)
        return "";
    else
        return reverse(head.getLink()) + head.getData();
}

:

public String reverse(IntNode head) {
    return (head == null)? "" : reverse(head.getLink()) + head.getData();
}

Answer 2

, . 2 ( , ):

• : , ( )
• : ,

2 , 1. , :

• head null

• head - IntNode:

  . head.getLink() null

  . head.getLink() IntNode:

  • head.getLink().getLink() null

  • head.getLink().getLink() IntNode

; , 2 :

• head null
• head - IntNode

head IntNode, head.getLink() ( ), 2 , , head null ( ).

---

, , IntNode (.. head.getData()); reverse(), , .

Answer 3

, , . .

Q1. ? []

A1. . []

---

Q2. ? [1]

2. . [1]

---

Q3. ? [1 2]

A3. , . [2 1] ( )

---

Q4. ? [1 2 3]

A4. , . [3 2] + [1] = [3 2 1]

---

: N - N - 1 ).

What is our base case? From the above, a list of 1 or 0 elements appears. Take a closer look, applying our template to a list of length 1, we will see that [1] is changed to [] with the first element added, that is, [] + [1]. So our base case is just an empty list.