题解 | #反转链表#

解题思路

依然记得这是我面试AMD时mentor给我出的一道题，以前的做法都采用容器去做，今天思考了一些如果不使用容器应该怎么做呢??
首先考虑到反转，意味着逆序；逆序能联想到stack或者是链表插入法中的头插法。
所以本题采用头插法的写法。并且不产生额外的空间。d
我们定义一个ans节点表示最终返回的答案，采用头插法插入p节点，p是原链表的游标节点。
本题的注意点之一就是插入反转链表第一个节点的时候注意将下标设置为空指针。

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

        while(p){
            if(!ans)
            {
                ans = p;
                p = p->next;
                ans->next = nullptr;
            }
            else{
                // ListNode* ans_next = ans;
                ListNode* p_next = p->next;
                p->next = ans;
                ans = p;
                p = p_next;
            }
        }
        return ans;
    }
};