使用递归打印链表元素

Question

我正在解决Hackerrank上的反向打印挑战

void ReversePrint(Node* head)方法只有一个参数——链表的头。你不应该阅读来自stdin/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

注:节点的结构为结构节点{int数据;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';
}

Answer 2

如果您想返回反向链表:

  Node* List::reverseList()
{
    if(head == NULL) return;
    Node *prev = NULL, *current = NULL, *next = NULL;
    current = head;
    while(current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Answer 3

您可以递归地反转链表，然后打印链表。

Node* reverse(Node* node) 
{ 
    if (node == NULL) 
        return NULL; 
    if (node->next == NULL)
    { 
        head = node; 
        return node; 
    } 
    Node* temp= reverse(node->next); 
    temp->next = node; 
    node->next = NULL; 
    return node;
}