反转链表（不带头指针&带头指针）

/* 题目给出的链表数据结构
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
}; 
1.记录原链表下一个节点 防止断链
2.将原链表头节点插到新链表中
3.重新设置两个链表的头节点
注意：带头指针初始化与不带头指针初始化的区别，其他大致相同。
*/
// 不带头指针
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *cur = pHead, *nex; // cur 当前节点 , nex 当前节点的下一个节点，记录指针防止断链
        pHead=NULL; // 初始化新链表的头节点 
        while(cur)
        {
            nex = cur->next; // 记录当前节点的下一个节点，防止断链
            cur->next = pHead; // 将当前节点插到新链表的头节点
            pHead = cur; // 重新设置新链表的头节点
            cur = nex; // 重新设置原始链表头节点
        }
        return pHead;
    }
};
/*
带有头指针的链表
*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *cur = pHead->next, *nex; // cur 当前节点 ，nex 当前节点的下一个节点
        pHead->next = NULL;//初始化头指针
        while(cur)
        {
            nex = cur->next; // 记录头节点的下一个节点，防止断链
            cur->next = pHead->next; // 将当前节点插到新链表的头指针的后面
            pHead->next = cur; 
            cur = nex; // 重新设置原始链表头节点
        }
        return pHead;
    }
};