以相反的顺序打印单链表

Question

好吧，这是在路易斯安那州东南部大学的CMPS 280考试中的奖金问题。以三行反向打印单链表。有任何想法吗？

Answer 1

C实施您的奖金问题，分三行：

#include <stdio.h>

struct node {
    int data;
    struct node* next;
};

void ReversePrint(struct node* head) {
    if(head == NULL) return;
    ReversePrint(head->next);
    printf("%d ", head->data);
}

int main()
{
    struct node first;
    struct node second;
    struct node third;

    first.data = 1;
    second.data = 2;
    third.data = 3;

    first.next = &second;
    second.next = &third;

    ReversePrint(&first); // Should print: 3 2 1
    printf("\n");

    return 0;
}

Answer 2

如果允许使用其他数据结构，则使用堆栈。

步骤1：从头节点遍历链表并将密钥放入堆栈，直到到达最后一个节点。这将花费O（n）时间。

第2步：从堆栈中弹出元素。这将花费O（1）时间。

因此，代码将是

while(head != null){
stack.push(head.val);
head = head.next;
}
while(stack.isEmpty() != true){
stack.pop();
}

Answer 3

通常，在SO上寻求帮助时，您应该首先尝试自己解决问题。然后，如果你遇到困难，请到目前为止来看看你做了什么，并清楚地表明你的问题是什么，以最大限度地获得帮助的机会。

How to ask a good question on SO

但是，因为它是一个过去的考试问题，我的答案不会帮助你作弊:)，这里的伪代码如何递归地执行：

reversePrint(head)
    if head is null then return // Line 1: base case
    reversePrint(head.next)     // Line 2: print the list after head
    print(head.data)            // Line 3: print head

Answer 4

以下是不同的方法。完整的源代码可以在下面找到超链接。

1）使用额外的记忆打印：https://www.geeksforgeeks.org/print-reverse-linked-list-using-stack/

2）使用递归打印：https://www.geeksforgeeks.org/print-reverse-of-a-linked-list-without-actually-reversing/

3）通过修改原始列表进行打印 - 即首先反转列表然后从开始打印。

倒车清单的源代码：https://www.geeksforgeeks.org/reverse-a-linked-list/

4）不使用额外空间或修改原始列表进行打印：https://www.geeksforgeeks.org/print-reverse-linked-list-without-extra-space-modifications/

5）使用回车（“r”）打印：https://www.geeksforgeeks.org/an-interesting-method-to-print-reverse-of-a-linked-list/

Answer 5

下面是我没有堆栈的迭代Java解决方案。我想空间复杂度仍然是O（n），因为StringBuilder的长度随着列表中项目的数量线性增长。但是，我们可以在不使用堆栈（数据结构或递归调用堆栈）的情况下离开，如果我们所做的只是将元素打印到控制台，那么这两者都不是必需的。此外，迭代堆栈解决方案使用两个循环，而此方法仅需要一个循环。最后，时间复杂度仍然是O（n），这比Geeks在另一个答案中引用的Geeks的二次算法要好得多。

void printInReverse(ListNode head) {
  StringBuilder sb = new StringBuilder();

  ListNode n = head;
  while (n != null) {
    sb.insert(0, "<-" + n.data);
    n = n.next;
  }

  System.out.println(sb.toString());
}