/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

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

 * };

 */

class Solution {

public:

    ListNode* recursive(ListNode* head) {

        ListNode* pre_node;

        if(head->next!=NULL)

        {

            pre_node=recursive(head->next);

            ListNode* cur_pre_node=pre_node;//找到新的节点后，对末尾加入当前节点

            while(cur_pre_node->next!=NULL)

                cur_pre_node=cur_pre_node->next;

            cur_pre_node->next=head;

            head->next=NULL;//别忘了末尾补NULL

        }

        else

            pre_node=head;//如果是尾节点，就定义为新的头结点

        return pre_node;

    }

    ListNode* iteration(ListNode* head)

    {

        ListNode* node=new ListNode(head->val);

        head=head->next;

        while(head!=NULL)

        {

            ListNode* cur_node=new ListNode(head->val);//每次开辟新空间

            cur_node->next=node;//指向node

            node=cur_node;//node后移

            head=head->next;

        }

        return node;

    }

    ListNode* reverseList(ListNode* head) {

        if(head==NULL)

            return NULL;

        //return recursive(head);//方法一 递归

        return iteration(head);//方法一 迭代

    }

};