#include <iostream>
#include <algorithm>
#include "string.h"
#include "stdio.h"
#include <vector>
#include <deque>
#include<stack>
using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Reverse {
public:
　　//非递归实现
    ListNode* chkIntersect(ListNode* headA) {
        ListNode* head = NULL;
        ListNode* pNode = headA;
        ListNode* preNode = NULL;
        while(pNode !=NULL)
        {
            ListNode* pNext = pNode->next;
            if(pNext == NULL)
                head = pNode;
            pNode->next = preNode;
            preNode = pNode;
            pNode = pNext;
        }
        return head;
    }
　　//递归实现
    ListNode* chkIntersect1(ListNode* headA) {
        ListNode* pNode = headA;
        ListNode* node = chk(pNode,headA);
        cout<<headA->val<<endl;
        cout<<node->val<<endl;
        node->next = NULL;
        return headA;
    }
    ListNode* chk(ListNode* pNode,ListNode* &headA) {
        if(pNode == NULL || pNode->next == NULL)
        {
            headA = pNode;
            return pNode;
        }
        else
        {
            ListNode* node = chk(pNode->next,headA);
            node->next = pNode;
            node = node->next;
            return node;
        }
    }
};

int main() {

    vector<int> res;
    res.push_back(1);
    res.push_back(2);
    res.push_back(3);
    res.push_back(4);
    res.push_back(5);
    
    vector<int> nxt;
    nxt.push_back(1);
    nxt.push_back(2);
    nxt.push_back(3);
    nxt.push_back(4);
    nxt.push_back(0);

    ListNode* pRoot = new ListNode(res[0]);
    ListNode* preNode = pRoot;

    int i=0;
    while(nxt[i]!=0)
    {
        ListNode* curNode = new ListNode(res[nxt[i]]);
        i++;
        preNode->next = curNode;
        preNode = curNode;
    }
    Reverse solution;

    ListNode* node=solution.chkIntersect1(pRoot);
    while(node)
    {
        cout<<node->val<<" ";
        node=node->next;
    }
    return 0;
}