反向打印链接列表的元素

Question

我正在练习我的数据结构，并尝试以相反的顺序打印this problem on HackerRank来打印链表的元素。

我已经多次浏览了我的解决方案，但是我不明白为什么这是错误的。

我的解决方案：

    static void reversePrint(SinglyLinkedListNode head) {
        if (head==null){
            return;
        }

        ArrayList<Integer> intList = new ArrayList<>();

        while(head!=null){
            intList.add(head.data);
            head = head.next;
        }

         Collections.sort(intList, Collections.reverseOrder());
        for(int i: intList){
            System.out.println(i);
        }
    }

感谢有人可以帮助指出我的错误。

Answer 1

使用Stack而不是ArrayList

static void reversePrint(SinglyLinkedListNode head) {
    if (head==null){
        return;
    }

    Deque<Object> intList = new ArrayDeque<>();
    while(head!=null){
        intList.push(head.data);
        head = head.next;
    }

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

Answer 2

感谢有人可以帮助我指出我的错误

问题

[您使用的行为是ArrayList的First In First Out，因此，一旦for循环intList，打印的元素顺序与从head开始的链表中的顺序相同。] >

可能的解决方案

要解决您的问题，可以简单地：

1-使用intList始终将元素插入List#add(int index, E element)的零位置：

// ...
intList.add(0, head.data);
// ...
2-或者，您可以替换用于“还原”元素的数据结构。

例如，您可以使用任何Last In First Out数据结构，例如其LIFO变体中的Queue或Queue。

---

另一种选择

为您提供另一个完全的解决方案，您可以像这样递归地实现它：

Deque
如果head为Deque，请什么都不做，因为在这种情况下我们不应该打印任何内容。否则，首先static void reversePrint(SinglyLinkedListNode head) {
    if (head != null) {
        reversePrint(head.next);
        System.out.println(head.data);
    }
}
 null元素，然后是当前元素（reversePrint）...这将导致反转效果。

值得注意的是，这不会颠倒元素的顺序，也就是说，它不会修改每个元素的next。