206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

这道题经常被同事们戏称为“送分题”，比如你面试别人时特别想要那个人，那就给他出这个题。那意思是说这道题是个人就会，但是我见过不少人阴沟翻船的时候，原因可能是这道题太简单了，以至于刷题时都不屑于刷，到了面试这种高度紧张的场合，一着急写不出来了。所以大家不要掉以轻心，复杂总是起于简单，而且本题是解其他衍生题的基础，比如234. 回文链表，92. 反转链表 II。

一开始看这道题时我的想法是，既然你是要把链表反转，那我依次将每个节点的next指针换个方向不就行了，示意图如下。

代码如下。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur.next != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        cur.next = pre;
        return cur;
    }
}

后面看了答案，第一次知道了“头插法”，即不断的将“头”的后一个节点移到头的前一个节点，直到最后一个节点，示意图如下。

代码如下。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = head;
        while (cur.next != null) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = dummy.next;
            dummy.next = next;
        }

        return dummy.next;
    }
}

我个人觉得头插法写起来更简单紧凑，当然这是一个智者见智的问题，小伙伴们你怎么看？