206. [E] Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

这个题目之前去 Facebook 面试遇到过一个相关的题目，也是一个基本的链表技巧题目，很重要。可是时隔两个月，再次做的时候，虽然是个 Easy Level 的题目，可是思路还是会乱。所以重点记录一下。

反转链接的方法就是将当前节点c的 next 更新为上一个节点 p:

c.next = p

但是这样做的问题是，丢失了当前节点的下一个节点的链接。因此，需要引入一个临时节点 n，在翻转之前记录下当前节点的下一个节点。

所以，整个过程的要点是要有三个指针，分别是 p前一个节点，c当前节点，和n下一个节点。为了避免在翻转的过程中丢失链表链接，要用 n 来保存下一个节点。翻转完成之后，当前节点 c 成为下一次的前节点 p ，而保存过的 n 成为下一次的当前节点 c 。重复这个过程。

== 最开始 ==
(p=null)  (c/head) -> (..) -> (..)

== 中间过程 ==
初始状态： (.) <- (p) (c) -> (.) -> (.)
记录 n ：(.) <- (p)  (c) -> (n) -> (.)
反转 c ：(.) <- (p) <- (c) (n) -> (.)
更新 pc：(.) <- (.) <- (p) (c) -> (.)

==最终状态
(.) <- (p) (c) -> (null)

代码如下：

public ListNode reverseList(ListNode head) {
    ListNode p = null, c = head, n = null;
    while (c != null) {
        n = c.next; // 保存下一个节点
        c.next = p; // 反转当前节点连接
        p = c; // 陆续更新 p 和 n，次序很重要
        c = n;
    }
    return p;
}