反转链表

15. 反转链表

题目描述

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

解题思路：

通过3个指针遍历一遍链表，实现链表反转，详细过程参见（转载）漫画：如何将一个链表“逆序”？

解答：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(nullptr) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == nullptr || pHead->next == nullptr)
            return pHead;
        ListNode *p1 = pHead;
        ListNode *p2 = pHead->next;
        ListNode *p3 = nullptr;
        while(p2 != nullptr)
        {
            p3 = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = p3;
        }
        pHead->next = nullptr;
        pHead = p1;
        return pHead;
    }
};