#include <bits/stdc++.h>
using namespace std;

/*

         ---      ---      ---      ---    
head -->|   | -->|   | -->|   | -->|   | ---
         ---      ---      ---      ---    |
                                           v
                                         null


Recursion:

         
Interation: 
3 pointers: curr = head, next, prev = 0

   start                 loop
   ----                  ----
   curr = head           next = curr->next  // save curr->next
   next = curr->next     curr->next = prev (reverse)
   prev = nullptr        // move to next node
                         prev = curr
                         curr = next

         ---      ---     
      --|   | -->|   |
     |   ---      ---     
     v                    
    null
    
         ---      ---     
      --|   |<---|   |
     |   ---      ---     
     v                    
    null
                         
*/

struct Node
{
    int data;
    Node* next;
    
    Node(int new_data)
    {
        data = new_data;
        next = nullptr;
    }
};

Node* reverseListIteratively(Node* head)
{
    Node* curr = head, *prev = nullptr, *next;

    while (curr != nullptr)
    {
        // store next
        next       = curr->next;

        // reverse
        curr->next = prev;
        
        // move to next node
        prev       = curr;
        curr       = next;
    };

    return prev;
}

void printNode(Node* node)
{
    cout << string("reverseList node: ") << (node == nullptr ? string("nullptr") : to_string(node->data))
         << string(" node->next: ") << (node->next == nullptr ? string("nullptr") : to_string(node->next->data))
         << endl;
}

bool list_end = false;

Node* reverseListRecursive(Node* node)
{
    printNode(node);
    
    if (/*node == nullptr ||*/ node->next == nullptr)
        return node;
    
    Node* new_head = reverseListRecursive(node->next);

    // when reverseListRecursive intially returns new_head will be last node in list and node will
    // be the second to last node in the forward list (node->data = 4). Subsequent return will be
    // prior nodes in reverse, node-data=3, node->data=2, node->data=1
    
    
    cout << "--- unwind ---" << endl;

    if (list_end == false) { cout << " at list end\n"; list_end = true; }

    cout << " new_head: "             << new_head->data
         << " new_head->next: "       << (new_head->next == nullptr ? 0 : new_head->next->data)
         << endl;    


    cout << right << setw(25) << "before reverse: node: " << node->data << " node->next: " << (node->next == nullptr ? 0 : node->next->data)
         << " node->next->next: " << (node->next->next == nullptr ? 0 : node->next->next->data) << endl;

    //======================
    // reverse, point next->next to current node
    node->next->next = node;

    cout << right << setw(25) << "after reverse: node: " << node->data << " node->next: " << (node->next == nullptr ? 0 : node->next->data )
         << " node->next->next: " << (node->next->next == nullptr ? 0 : node->next->next->data) << endl;

    int data = node->next->data;

    //======================
    // This is done so the last node traversed will have next == nullptr
    node->next = nullptr;

    cout << right << setw(25) << "node: " << node->data << " node->next: " << data << " ===> node->next: nullptr" << endl;

    return new_head;
}


void printList(Node* node)
{
    cout << "list data: ";    
    while (node != nullptr)
    {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

int main(void)
{
    Node* nodes[5];
    for (auto& i: {4,3,2,1,0})
    {
        int data = i+1;
        nodes[i] = new Node(data);
        if (i==4)
            nodes[i]->next = nullptr;
        else
            nodes[i]->next = nodes[i+1];
    }
    Node* head = nodes[0];

    // Node* head = new Node(1);
    // head->next = new Node(2);
    // head->next->next = new Node(3);
    // head->next->next->next = new Node(4);
    // head->next->next->next->next = new Node(5);

    printList(head);
    head = reverseListRecursive(head);
    printList(head);    
    return 0;
}