题解 | #反转链表#
反转链表
http://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca
首先这道题要求空间复杂度为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;
}