面试题16 反转链表

题目链接：面试题16 反转链表

我的思路

1. 反转链表的基本思路就是把指向后驱的指针指向前驱
2. 如果把指针的指向改变，无法继续遍历链表，所以需要辅助指针
3. 一句话秒杀：指针指向前驱，前驱节点后驱

实现代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //反转后头指针
        ListNode* pReversedHead = NULL;
        //遍历指针
        ListNode* pNode = pHead;
        //前驱指针
        ListNode* pPrev = NULL;
        while(pNode != NULL)
        {
            ListNode* pNext = pNode->next;
            if(pNext == NULL)
                pReversedHead =pNode;
            pNode->next=pPrev;
            pPrev=pNode;
            pNode=pNext;
        }
        return pReversedHead;
    }
};