每日算法题：反转链表

描述（来自牛客）：

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

解题思路：

（1）众所周知，链表是由data和next组成的，而next只能指向后续结点。

（2）如果链表只有2个结点，比如1->2，那反转的方法就是：先断开1到2的连接（即结点1的next，因为不允许1->2和2->1同时存在），然后1->NULL（因为链表的最后一个结点的next为空），最后2->1（即2的next指向1），并且第二步和第三步的顺序无所谓。

（3）扩展到3个以及更多的情况，比如1->2->3，如果还用上面的方法，就会导致当2->1之后，原有的2->3没了（因为2的next只能指向一个位置，改成1之后就找不到3了），而3只能通过它的前续结点找到，现在通过2只能找到1了，3就变成了一个无法访问的结点，这是很危险的。

（4）所以应该在修改2的next之前，就先找到3，这样2->1之后，仍然可以访问3。

（5）因此应该定义3个指针，分别表示前续，当前和后续的结点位置。每一轮修改next前，先把后续的指针更新，然后修改，最后把前续指针改成当前指针，后续指针改成当前指针，这样就能顺利进行下一轮修改了。

源代码：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pre = NULL;
        ListNode* cur = pHead;
        ListNode* tmp = NULL;
        while(cur != NULL){
            tmp = cur->next; // 找到后续结点
            cur->next = pre; // 修改当前next
            // 更新
            pre = cur;
            cur = tmp;
        }
        return pre; // 最后输出链表的头结点（即原链表的尾结点）
    }
};