反转链表-哨兵

一、递归

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {

        if(  (nullptr==pHead)||nullptr==(pHead->next) )
        {
            return pHead;
        }

        ListNode * ret=ReverseList( pHead->next );
        //下面的代码，还可以优化，画图知道用pHead->next->next=pHead;能抵挡过下面的4行
        ListNode * temp=ret;
        while( nullptr!=(temp->next) )
        {
            temp=temp->next;
        }
        temp->next=pHead;
        pHead->next=nullptr;

        return ret;
    }
};

二、迭代——单哨兵解法

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode * ret=nullptr;

        while( nullptr!=pHead )
        {
            ListNode * temp=pHead->next;
            pHead->next=ret;
            ret=pHead;

            pHead=temp;
        }

        return ret;
    }
};