如何在 Java 中不使用递归打印反向链表？

Question

我尝试打印一个没有递归的反向链表并反转链表。我该怎么做？

问题：如何在不使用递归且不反转列表的情况下打印反向链表？

要求: 没有额外的space，不能反转链表，不能使用递归。

这里是链表节点的定义

class Node {
  int value;
  Node next;

  public Node(int val) {
    this.value = val;
  }
}

这是我的 printReverseLinkedList 的递归版本：

public void printReverseList(Node head) {
    Node temp = head;
    if (temp.next != null) {
        printReverseList(temp.next);
    }
    System.out.print(temp.value);
}

性能无所谓，因为我就是想做成这样。

Answer 1

你可以试试这个：

public void printReverseList(Node head) {
            if(head == null) return;
            Node prev = null;
            Node revers = head;
            Node nex = null;

            while (revers != null){
                nex = revers.next;
                revers.next = prev;

                prev = revers;
                revers = nex;

            }
            System.out.println(prev);
        }

Answer 2

如果你既不能反转列表，也不能使用递归，唯一的方法是：

public void printReversList(Node head) {

    Node current = head; // used to search through the list
    Node last    = null; // stores the last element that we printed

    while (last != head) { // = we didn't print everything yet

        // find next element to print - it's one element before we reach "last"
        while (current.next != last) {
            current = current.next;
        }

        // Store the current element as the new last and print it
        last  = current;
        system.out.print(last.value);

        // reset current and start all over
        current = head;
    }
}

非常无效，但我想不出别的办法。

Answer 3

使用堆栈然后弹出如何？你说使用另一种数据结构就可以了。这不是很好的代码，但是应该可以完成工作。

public void printReversList(Node head) {

    Stack<Node> stack = new Stack<>();

    while (head != null){

       stack.push(head);
       head = head.next;          
   }

   while (!stack.isEmpty()){
       System.out.println(stack.pop());
   }
}

Answer 4

void ReversePrint(Node head) {
    // This is a "method-only" submission.
    // You only need to complete this method. 
    Stack<Node> stk=new Stack<>();

    Node temp=head;
    while(temp!=null){
        stk.push(temp);
        temp=temp.next;
    }
    while(!stk.isEmpty()){
        System.out.println(stk.pop().data);
    }
}

Answer 5

public void printReverseList(Node head) {
        Node node = head;
        List<Integer> list = new ArrayList<Integer>();
            if (head == null){
                System.out.println(head.data); 
            }
            else{
               while (node != null){
                list.add(0, node.data);
                node = node.next;
            }
            for (int item:list){
                System.out.println(item);
            }
        }
    }

如何在 Java 中不使用递归打印反向链表？

How to print a reverse linked list without using recursion in Java?

java

iteration

recursion

linked-list

singly-linked-list