题解 | #反转链表#

首先这道题要求空间复杂度为O(1),所以不能使用栈来解决。
之后我们考虑在链表原有的基础上进行逆序，先手动给他实现一下（图丑见谅）

是不是感觉看上去是不是很简单，现在我们来思考一下计算机如何实现。

分析

首先，题目给了一个pHead指针，我们在图里给他加上
可以看到由（1）到（2）仅需pHead一个指针就能完成。操作如下：

pHead->next->next=pHead;

但我们可以观察到，仅用一个指针无法从（2）到（3）

为了实现从（2）到（3），我们需要将结点3的next置为结点2，因此，我们还需要一个指向结点3的指针。而我们知道，经过上一步的操作，（2）中的pHead仍指向结点1，而我们要实现由结点3指向结点2，因此还需要一个指向结点2的指针。 如下图所示

到此，问题似乎是解决了，下面我们假设两个指针分别是pHead和q,
指针q可由q=q->next进行移动，指针pHead可由pHead=pHead->next进行移动；
但是我们要注意，反向操作也与pHead有关（pHead->next->next=pHead;）我们要保证pHead->next->next=pHead在pHead=pHead->next前执行，否则我们无法找到当前结点的前一结点，
1. 但这样我们又无法用pHead=pHead->next向后移动pHead； 由于q=pHead->next，我们又想到pHead=q移动pHead，此时q=q->next要在最后执行，
2. 可是因为当前结点已指向前一结点，因此q=q->next无法找到下一个结点。 因为几个操作之间形成了环，所以两个指针无法实现。几种无法实现的原因如下图所示：

实现

因此，我们需要在添加一个指针保存状态，我们设它为q。 我们要进行的操作为p、pHead、q移动加反向。可以看到此时几个操作虽有一定的先后顺序，但未形成环

代码如下所示：

p=NULL;
q=pHead->next;
while(){	//先不考虑循环条件
	p=pHead;	//p的移动
    pHead=q;	//pHead的移动
    q=q->next;	//q的移动
    pHead->next=p;	//反向
}

我们看到图里这个情况上述代码不能很好解决，因此我们一开始就要将其处理成下图所示

p=NULL;
q=pHead->next;
pHead->next = p;

接下来我们考虑循环里的条件，我们知道最后面的指针是q，因此，当q不为空时，一直执行。

p=NULL;
q=pHead->next;
pHead->next = p;
while(p！=NULL){
	p=pHead;	//p的移动
    pHead=q;	//pHead的移动
    q=q->next;	//q的移动
    pHead->next=p;	//反向
}

此时我们需要考虑几种特殊情况：

• 拥有单个结点的链表：我们可以看到，该链表不进入循环，可直接返回
• 空链表：这种情况要注意上面的循环条件会报错，因此需要特殊处理

完整代码如下：

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    if (pHead == NULL) return pHead;	//处理特殊情况——空链表
    struct ListNode* p, *q;
    p = NULL;
    q = pHead->next;
    pHead->next = p;
    while (q!= NULL) {
        p=pHead;
        pHead=q;
        q=q->next;
        pHead->next=p;
    }
    return pHead;
}