Interview question: How to implement an efficient one-way list reverse output

The problem: How to implement an efficient one-way list reverse output?

People draw: Alibaba expert: Yun Long/Aliyun Elastic artificial intelligence principal

Refer to the answerHere is one of the ways to write it, but there are also different ways to write it, such as recursion. For your reference.

In this problem, we need to reverse a linked list. Because linked lists have no subscripts, we can only reverse them with the next point of the node. The Java reference code is as follows:

package com.tntxia.basic;

import java.util.Stack;

class Solution<T> {

    public LinkNode<T> reverse(LinkNode<T> head) {
       if (head == null || head.next == null) {
    	   return head;
       }
       LinkNode<T> currentNode = head;
       Stack<LinkNode<T>> stack = new Stack<>();
       while(currentNode ! =null) {
    	   stack.push(currentNode);
    	   LinkNode<T> tempNode = currentNode.next;
    	   currentNode.next = null; 
    	   currentNode = tempNode;
       }
       
       head = stack.pop();
       currentNode = head;
       
       while(! stack.isEmpty()) { currentNode.next = stack.pop(); currentNode = currentNode.next; }returnhead; }}public class LinkNode<T>{
	T val;
	public LinkNode(T val) {
		this.val = val;
	}
	LinkNode<T> next;
	
	public void print(a) {
		LinkNode<T> current = this;
		while(current ! =null){ System.out.println(current.val); current = current.next; }}public static void main(String[] args) {
		Solution<Integer> sol = new Solution<Integer>();
		LinkNode<Integer> head = null;
		LinkNode<Integer> current = null;
		for(int i = 1; i<=100; i++) {if (current == null) {
				current = new LinkNode<Integer>(i);
				head = current;
				continue;
			}
			current.next = newLinkNode<Integer>(i); current = current.next; } head.print(); head = sol.reverse(head); head.print(); }}Copy the code