反转链表(C++)

方法一：利用栈实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        stack<ListNode*> s;
        if(pHead==NULL||pHead->next==NULL)
            return pHead;
        ListNode* p = pHead;
        while(p->next)
        {
            s.push(p);
            p = p->next;
        }
        ListNode* head = p;
        while(!s.empty())
        {
            p->next = s.top();
            p = p->next;
            s.pop();
        }
        p->next = NULL;

        return head;
    }
};

双指针法：

class Solution{
public:
    ListNode* ReverseList(ListNode* pHead)
    {
         if(pHead==NULL)
            return pHead;
        ListNode* cur = pHead;
        ListNode* pre = NULL;
        while(cur!=NULL)
        {
            ListNode* pNext = cur->next;
            cur->next = pre;
            pre = cur;
            cur = pNext;
        }   
        return pre;
    }
};