/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//-----------------------------

// 迭代版本
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 空链表 或者 只有一个节点   
        if( !head || !head->next ) return head;
        auto p = head, q = p->next;
        while(q)
        {
                auto c = q->next;
                q->next = p;
                p = q, q = c;
        }
        head->next = NULL;
        return p;

    }
};

// 递归版本
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
            if( !head || !head->next ) return head;  // 边界

            // 递归
            auto tail = reverseList( head->next );
            head->next->next = head;
            head->next = NULL;

            // 最后返回的head
            return tail;
    }
};