Have the audacity to give everyone a thumbs-up, ha ha ha! Creation is not easy, I hope you can encourage.

Today we are going to talk about “reverse output one-way linked list”, which is also a relatively common interview question. Our company recently asked this question when recruiting, but some of them couldn’t answer. Therefore, I want to write an article to record several solutions I know, in case of need, and also hope to help those in need.

The following are covered: “Linked list data structures, recursive algorithms, stacks.” If you are not familiar with these, you can take a look at the previous article, which has a detailed introduction.

What is a reverse output unidirectional list

I’m sure you can get a sense from the literal meaning, the so-called reverse output one-way linked list is to print the list from the end of the list. Doesn’t that sound like an easy thing to say.

Ok, so now let’s do it.

The first solution

First flip the original list and then print the flipped list.

This approach is not demonstrated here, but if you are not familiar with reversed lists, check out the previous article on “reversed unidirectional lists”. I do not recommend using this method, because it is inefficient to create an additional linked list.

Second solution

The reverse printing of linked list is realized by recursion.

Code display:

/** * outputs the linked list in reverse order (using recursion) **@param node
 */
public void showNode(Node node){
    if(node.next ! =null) {// Recursive call itself without reaching the end of the list.
      showNode(node.next);
    }
    // Outputs the node content
    System.out.println(node.data);
}
Copy the code

Each time a method is called to determine whether there is another node in the list, if there is, the recursive call itself, until the end of the list ends the recursive call. It then outputs the contents of each node in turn from the end of the list. Why each node is output from the end of the list should be clear to anyone who knows recursion. If you don’t understand it, you can refer to the previous article.

Third solution

Implementation idea: through the stack structure “advanced after out” characteristics to achieve the reverse output of the linked list.

Code display:

/** * reverse output linked list (using stack) */
public void reversePrint(Node headNode) {
    if (headNode == null || headNode.next == null) {
      return;
    }
    // Initialize the stack
    Stack<Node> stack = new Stack<>();
    // Create temporary variables
    Node cur = headNode.next;
    while(cur ! =null) {
      // List nodes are pushed
      stack.push(cur);
      // Move the variable back
      cur = cur.next;
    }
    / / flare stack
    while (stack.size() > 0) { System.out.println(stack.pop().data); }}Copy the code

The code explains: each time the loop from the list of nodes pushed on the stack, until the entire list of nodes pushed on the stack. In turn the stack of data pop up, so as to achieve the reverse output of the linked list.

conclusion

These are the three ways I know how to output a one-way list in reverse order. If there is a better way, let me know in the comments section. This is the end of today’s sharing, if there is any question in the article, I hope you can put forward, I will actively modify, humbly learn, thank you.