使用递归打印链接列表元素

Question

我在Hackerrank的反向挑战中解决了Print问题

该void ReversePrint(Node* head)方法采用一个参数 - 链表的头部.你不应该从stdin/console读取任何输入.头部可能是空的,因此不应打印任何东西.以相反的顺序将链接列表的元素打印到stdout/console(使用printf或cout),每行一个.

样本输入

1 - > 2 - > NULL

2 - > 1 - > 4 - > 5 - > NULL

样本输出

2
1
5
4
1
2

我用这个解决了它

    #include <vector>
    void ReversePrint(Node *head)
{
  // This is a "method-only" submission. 
  // You only need to complete this method. 

    std::vector<int> nodeList;
    if(head != NULL){

        while(head != NULL){
            nodeList.push_back(head->data);
            head = head->next;            
        }

        for (std::vector<int>::iterator it = nodeList.end()-1 ; it != nodeList.begin()-1; --it){
            std::cout << *it <<endl;
       }
    }

}

它工作得很好,但扩展到使用递归提供了错误的答案,为什么会发生这种情况？

std::vector<int> nodeList;
void ReversePrint(Node *head){
    if(head != NULL){
        nodeList.push_back(head->data);
        ReversePrint(head->next);
    }
    else{
        for (std::vector<int>::iterator it = nodeList.end()-1 ; it != nodeList.begin()-1; --it){
            std::cout << *it <<endl;
       }

    }

}

结果是

2
1
5
4
1
2
2
1

注意:Node的结构以struct Node {int data; struct Node*next; }

Answer 1

为什么这么复杂？

/* Function to reverse print the linked list */
void ReversePrint(Node* head)
{
    // Base case  
    if (head == NULL)
       return;

    // print the list after head node
    ReversePrint(head->next);

    // After everything else is printed, print head
    std::cout << head->data << '\n';
}