反转链表（C++）

刷题平台

牛客网

题目描述

输入一个链表，反转链表后输出新链表的表头。

解题思路

题目中给出的输出新链表的表头，根据给出的代码初定义ListNode *ReverseList(ListNode *pHead) {}可知这个“表头”的含义不是指单一的元素，而是反转后的整个链表。（自己理解，不知对错）

• 通过三个指针来完成反转，pCurr是指向当前结点的指针，pPre指向当前结点之前的结点，pNext指向当前结点之后的结点。

代码

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

class Solution
{
public:
    ListNode *ReverseList(ListNode *pHead)
    {
        if (pHead == NULL)
            return NULL;
        ListNode *NewHead = NULL; // 反转后的链表
        ListNode *pCurr = pHead;
        ListNode *pPre = NULL;
        while (pCurr != NULL)
        {
            ListNode *pNext = pCurr->next;
            if (pNext == NULL)
                NewHead = pCurr;
            pCurr->next = pPre; // 反转，即将当前结点的指针由指向next指向pre
            pPre = pCurr;
            pCurr = pNext;
        }
        return NewHead;
    }
};

运行的过程

​ P为当前结点的前一个指针，C为当前结点的指针，N为当前结点的下一个指针。

---

参考文献：牛客网。