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

/*
  
Interation: 
3 pointers: curr,  next, prev

   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

  Initialize: curr = head, prev = null, next = curr->next

----  
1.
----
         ---     ---     ---     ---    
head -->| 1 |-->| 2 |-->| 3 |-->| 4 |---> null
         ---     ---     ---     ---    

----
2.
----
         curr
          |
          v
         ---     ---     ---     ---    
head -->| 1 |-->| 2 |-->| 3 |-->| 4 |---> null
         ---     ---     ---     ---    
    prev -> null   
    next -> null

----
3.
----
prev     curr    next
 |        |       |
 |        v       v
 v       ---     ---     ---     ---    
null<-- | 1 |   | 2 |-->| 3 |-->| 4 |---> null
         ---     ---     ---     ---    

----
4.
----
         prev     curr   next
          |        |      |
          v        v      v
         ---     ---     ---     ---    
null<-- | 1 |<--| 2 |   | 3 |-->| 4 |---> null
         ---     ---     ---     ---    

----
5.
----
                 prev    curr    next      
                  |       |       |  
                  v       v       v  
         ---     ---     ---     ---    
null<-- | 1 |<--| 2 |<--| 3 |   | 4 |---> null
         ---     ---     ---     ---    

----
6.
----
                         prev    curr   next      
                          |       |      |  
                          v       v      v  
         ---     ---     ---     ---    
null<-- | 1 |<--| 2 |<--| 3 |<--| 4 |   null
         ---     ---     ---     ---    

----
7.
----
                                 prev   curr      
                                  |      |  
                                  v      v  
         ---     ---     ---     ---    
null<-- | 1 |<--| 2 |<--| 3 |<--| 4 |   null
         ---     ---     ---     ---    

----
8.
----
         ---     ---      ---     ---    
head--->| 4 |<--| 3 |<-- | 2 |<--| 1 |---> null
         ---     ---      ---     ---  
                                         
*/

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

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

    auto print = [](Node* node)
    { return node == nullptr ? "nullptr" : to_string(node->data); };

    cout << "start reverse: curr = head, loop while (curr != nullptr)\n";    
    while (curr != nullptr)
    {
        cout << "curr: " << curr->data << endl;
        
        // store next
        next = curr->next;
        cout << format("  store next: next = {}\n", print(next));
        
        // reverse
        curr->next = prev;
        cout << format("  reverse curr->next: {}\n", print(curr->next));
        
        // move to next node
        prev       = curr;
        curr       = next;
        cout << format("  move to next node: prev={} curr={}\n ", print(prev), print(curr));
    };

    // returns last node
    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->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 returns 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 ? "nullptr" : to_string(new_head->next->data))
         << endl;


    cout << right << setw(25) << "before reverse: node: " << node->data << " node->next: " << (node->next == nullptr ? "nullptr" : to_string(node->next->data)) << " node->next->next: " << (node->next->next == nullptr ? "nullptr" : to_string(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 ? "nullptr" : to_string(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;
}


/*
                         node  new_head
                          |       |                                 
                          v       v
         ---     ---     ---     ---    
head -->| 1 |-->| 2 |   | 3 |<--| 4 |
         ---     ---     ---     ---
                          | next 
                          V 
                         null
                 node          new_head         
                  |               |                                 
                  v               v    
         ---     ---     ---     ---    
head -->| 1 |   | 2 |<--| 3 |<--| 4 |
         ---     ---     ---     ---
                  | next
                  V
                 null
        node                   new_head 
          |                       |                                 
          v                       v    
         ---     ---     ---     ---    
        | 1 |<--| 2 |<--| 3 |<--| 4 |
         ---     ---     ---     ---
          | next
          v
         null
*/
Node* reverseListRecursiveNoPrint(Node* node)
{
    if (node->next == nullptr)
        return node;
    
    Node* new_head = reverseListRecursiveNoPrint(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.
    // Subsequent returns will be prior nodes in reverse

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

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

    // when recusrion ends new_head will be returned
    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];

    {
        cout << "------------ Iterative -----------\n";        
        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);
        Node* new_head = reverseListIterative(head);
        printList(new_head);
    }
    {
        cout << "------------ Recursive -----------\n";        
        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);
        Node* new_head = reverseListRecursiveNoPrint(head);
        printList(new_head);        
    }    
    return 0;
}