题目

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
下面给出链表定义：

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};

分析

题目描述有三个关键点：

1. 输入头结点
2. 反转链表
3. 输出反转后的头结点

其中，最核心的是【反转链表】

反转链表的关键点：

1. 保存要修改结点的下一结点
2. 保存要修改结点的上一结点
3. 最后修改结点指向
4. 注意“断链”问题，注意首尾节点问题

算法实现

ListNode* ReverseList(ListNode* pHead)
{
    ListNode* pReversedHead = NULL;
    ListNode* pNode = pHead;
    ListNode* pPrev = NULL;
    while(pNode != NULL)
    {
        ListNode* pNext = pNode->m_pNext;

        if(pNext == NULL)
            pReversedHead = pNode;

        pNode->m_pNext = pPrev;

        pPrev = pNode;
        pNode = pNext;
    }

    return pReversedHead;
}