正面刚算法-单链表反转（附记忆窍门）

单链表反转

单链表反转通俗表达：链上的后置指针全部倒戈。大家集体向后转，链头变链尾。

一道很基础但很考验对于链表掌握熟练度和细心程度的算法题。（代码量很适合用来白板书写）

先现思路

包含了两种实现思路，第一种就是把原来的链进行重新排序，依次移动链头和后续结点位置，实现反转（从图上看感觉有点像冒泡），另外一种实现就是用新链替换旧链。我自己实现了第一种；看答案发现答案的实现就是我考虑的第二种解法；）。

第一种实现

依次提升

手工版的第一次进行位置变动：

手画图：第一次“换头”

语言描述就是
每一次：
①原链的头结点指向新结点的后置结点；
②头结点被新结点后置指针指向；
③新结点成为头结点；

 /**
     * 单链表反转，依次转向
     * @param head
     */
    public static SingleLinkedList.Node reverse(SingleLinkedList.Node head) {

        if (null == head || head.next == null) {
            return head;
        }
        // 新的头结点
        SingleLinkedList.Node newHead = null;
        // 末尾节点
        SingleLinkedList.Node lastNode = head;
        SingleLinkedList.Node currentNode = head;
        // 依次取链中数据
        while (currentNode.next!=null){
            if (null != newHead){
                lastNode = newHead;
            }

            // 记录即将成为头结点的结点
            newHead = head.next;
            // 先拉住要动节点的后置节点，防止断链
            currentNode.next = newHead.next;

            // 新的头结点登基
            newHead.next = lastNode;
        }
        return newHead;
    }
/**
* 简化版
*/
    public static SingleLinkedList.Node reverse2(SingleLinkedList.Node head) {

        if (null == head || head.next == null) {
            return head;
        }
        // 新的头结点
        SingleLinkedList.Node newHead = null;
        // 末尾节点
        SingleLinkedList.Node lastNode = head;
        // 依次取链中数据
        while (head.next!=null){

            // 记录即将成为头结点的结点
            newHead = head.next;
            // 先拉住要动节点的后置节点，防止断链
            head.next = newHead.next;

            // 新的头结点登基
            newHead.next = lastNode;

            lastNode = newHead;
        }
        return newHead;
    }

第二种实现

依次获取结点，插入到新链中……

    public static Node reverse5(Node head) {
        Node curr = head, pre = null;
        while (curr != null) {
            // 老二准备
            Node next = curr.next;
            // 老老大就位
            curr.next = pre;
            // 新老大上位
            pre = curr;
            // 老二上位
            curr = next;
        }
        return pre;
    }

可能因为之前对算法研究较浅，有时候说不上来不同实现之间的本质区别，只能根据代码执行流程不同进行描述，甚至有时候觉得两种实现会很像。
比如我理解的单链表反转第二种实现：依次取出链中的结点，在新链进行头结点插入(链表的头插法)，就可以实现。如果仔细看上面的手画图，不难发现，新结点成为头结点不就是“头插法”吗？第一种实现中不执行标号为①的操作，就演变为了第二种实现！只是后面的代码用更少的指针实现（空间复杂度优）

根据代码，对比两种实现会发现：

第一种实现，每次循环结束链是没有断开的，依旧只有一条链；
第二种实现在循环中，会出现两条链，新链增长，老练变短，直至老链结点全部移到新链上。

总结

以上是我思考了若干天的总结，让我又一次体验到算法的神奇。关于第二种实现，上周日看了遍代码，只能隐约中可以在脑海中跑一遍代码。甚至有时候又不能复述出实现原理。在后面的两天里，我不时的回看这个算法，在脑海里反复的推演。最后是快把这个实现给“背“下来了，不能不能略显愚钝。
现在我的学习方法是，理解算法争取能在脑海里像玩积木一样，把这个处理流程给演义一遍

优点是形象生动，易于接受。
缺点：效率低；推理速度慢；每次都要像放电影一样，出错必须要从头再来。

目前我还未找到一条能躺着就学会数据结构和算法的道路，哈哈，只能正面刚了……

分享一个关于我总结出来记忆手写单链表反转的窍门（不喜轻喷）

回到前面第二个实现，我把实现过程用顺口溜的形式描述了下来。
历经几场风云变更：
1.【老二准备】理解为老队伍的老二待命，用一个临时变量（指针），标记老链表中第二个（next）结点。
2.【老老大就位】理解为老队伍的老大要准备上位了，怎么上位呢？骑到新队伍老大头上就可以了…，所以老的链头节点的后置结点改为指向新链的头结点。
3.【新老大上位】理解为就是接着上面的演，老队伍老大已经骑到新队伍前老大的头上了，但新老大的乌纱帽还没带上，带上新老大的官帽，大家就都认可他的地位了！所以新结点头结点为老头结点。
4.【老二上位】理解为现在老队伍的老大已经去当新队伍的头头了，老队伍里的已经待命的老二自然就当老队伍的的头头了，老链头结点点为标记的next结点。

结合代码，细细品味


  public static Node reverse5(Node head) {
        // pre:新链的头结点
        Node curr = head, pre = null;
        while (curr != null) {
            // 老二准备：【老二准备】理解为老队伍的老二待命，用一个临时变量（指针），标记老链表中第二个（next）结点。
            Node next = curr.next;
            // 老老大就位： 【老老大就位】理解为老队伍的老大要准备上位了，怎么上位呢？骑到新队伍老大头上就可以了…，所以老的链头节点的后置结点改为指向新链的头结点。
            curr.next = pre;
            // 新老大上位：【新老大上位】理解为就是接着上面的演，老队伍老大已经骑到新队伍前老大的头上了，但新老大的乌纱帽还没带上，带上新老大的官帽，大家就都认可他的地位了！所以新结点头结点为老头结点。
            pre = curr;
            // 老二上位：【老二上位】理解为现在老队伍的老大已经去当新队伍的头头了，老队伍里的已经待命的老二自然就当老队伍的的头头了，老链头结点点为标记的next结点。
            curr = next;
        }
        return pre;
    }