r：单链表全反转
先看这组链表
比如现在有这样一组链表：
head
↓
1 → 2 → 3 → 4 → null
保持图中各个节点的位置不动，我们要把节点之间的指向反过来：
null ← 1 ← 2 ← 3 ← 4
↑
head
原来 1 是头节点，没有前一个节点；反转之后，1 就变成尾节点，它的 next 应该指向 null，新的头节点则是 4。
从新的头节点 4 沿着 next 走，访问顺序就是 4 → 3 → 2 → 1 → null。变的是指针和遍历顺序，各个节点里的值没有交换。
一个节点里有什么？
先补一下节点这个知识点。这里的每个节点都有两个字段：
.value：这个节点保存的值。.next：指向下一个节点的引用。
注意，后面我们说的“当前节点”，指的是整个节点，不只是它里面的那个值。
我们用 c 表示当前节点，也就是 current。c.value 是它的值，c.next 是它指向的下一个节点。
反转链表的时候，value 不用动。我们要改的是节点之间的指向。
准备三个变量
开始之前，我们准备三个变量，分别保存前一个节点、当前节点，以及当前节点原来的下一个节点：
let p = null; // previous：前一个节点
let c = head; // current：当前节点
p 一开始等于 null，因为我们从头节点开始，它前面没有节点。
c 一开始等于 head，也就是链表的头节点。
还有一个 n，表示 next。它在每轮处理当前节点时保存：
let n = c.next;
为什么还要专门准备一个变量保存下一个节点？
改指向之前，先把后面的节点保存下来
我们回到这组链表上看：
1 → 2 → 3 → 4 → null
一个节点的 next 字段一次只能保存一个引用。可以有多个节点的 next 指向同一个节点，但是一个 next 不能同时指向两个节点。
所以，我们要改变 1 的指向，就得把它原来指向 2 的引用换掉。
但如果直接改，后面的 2 → 3 → 4 怎么办？我们就没法再通过 1.next 找到它们了。
所以，先换个地方保存：
let n = c.next;
这个东西保存好之后，就可以开始操作 c.next 了：
c.next = p;
第一轮里，c 是节点 1，p 是 null。所以这一步做完，就是：
c n
↓ ↓
1 → null 2 → 3 → 4 → null
你看，c.value 我们没有动，因为它不会变；c.next 也已经改好了。所以这个节点就处理完了，非常快。
接下来，就该准备处理下一个节点了。
把变量往后移动
现在要移动刚刚那几个变量，顺序是：
p = c;
c = n;
为什么这样移动？
因为当前节点已经处理好了。等到下一轮处理节点 2 时，它要指回的“前一个节点”，就是刚刚处理好的节点 1。
所以先让 p = c，把当前节点保存为下一轮的前一个节点。
然后，当前节点要换成谁？就是我们刚刚提前保存的那个下一个节点 n，所以 c = n。
这里要先保存 p = c，再移动 c。如果先把 c 改成 n，再写 p = c，p 保存的就不是刚刚处理好的那个节点了。
第一轮结束后：
p c
↓ ↓
1 → null 2 → 3 → 4 → null
这样就跑到下一个节点，开始下一轮循环了。
下一个节点也是一样的
现在 c 已经到了节点 2。
先保存它原来的下一个节点，也就是节点 3：
let n = c.next;
然后修改当前节点的指向：
c.next = p;
这时候 p 指向节点 1，所以这一步就是让 2 指向 1。
再移动变量：
p = c;
c = n;
第二轮结束后，就变成了：
p c
↓ ↓
2 → 1 → null 3 → 4 → null
后面也是一样，继续往后处理：
第三轮结束：
p c
↓ ↓
3 → 2 → 1 → null 4 → null
第四轮结束：
p c
↓ ↓
4 → 3 → 2 → 1 → null null
所以我们的循环条件就是：只要 c 还不等于 null，就一直做下去。
等 c 变成 null，说明所有节点都处理完了。这时候 p 指向的，就是反转后链表的头节点，所以最后返回 p。
完整代码
用 JavaScript 写出来就是这样。假设传进来的 head 是头节点，每个节点都有 value 和 next 字段，链表末尾的 next 是 null：
function reverseList(head) {
let p = null;
let c = head;
while (c !== null) {
let n = c.next; // 先保存原来的下一个节点
c.next = p; // 把当前节点的指向反过来
p = c; // 当前节点成为下一轮的前一个节点
c = n; // 继续处理原来的下一个节点
}
return p;
}
每一轮其实就四步：
- 保存下一个节点。
- 修改当前节点的指向。
- 让
p指向刚处理好的节点。 - 让
c移动到下一个待处理的节点。
整个过程没有交换节点里的值，改的都是 next。每个节点只处理一次，所以时间复杂度是 O(n)；只用了这几个变量，额外空间复杂度是 O(1)。
如果传进来的是空链表，c 一开始就是 null，循环不会执行，直接返回 null。如果只有一个节点，处理一轮之后返回的还是这个节点。
