反转单向链表

已知单链表的头部节点 head ，将链表反转,如图：

图1：单链表反转效果展示

我平时基本没看过算法，只有对链表的概念有基础的认知。看到这个题目，感觉并不难。但是要写起来，还是有点伤害脑细胞。

第一次做这个题目，代码写得并不简洁，并且花了20多分钟，而且在idea中反复调试才得到了正确结论。

链表类的算法题，指针的不断切换，总让人头晕...不知道你是否也有这样的感触。

尝试解题

以下是我第一次尝试解题的代码：

public static ListNode reverseList(ListNode head) {
       // 0.判断链表为空或者只有一个元素，无需反转
        if(head == null || head.next == null){
            return head;
        }


        ListNode pre = head;
        ListNode next = pre.next;
        ListNode temp;

        while(next != null){
            // 1.因为节点的next将指向前一个节点，临时缓存下一个节点
            temp = next.next;

            // 2.指向前一个节点
            next.next = pre;

            // 3.走到最后，跳出循环
            if(temp == null){
                break;
            }

            // 4.将next作为pre
            pre = next;
            // 5.将temp作为next
            next = temp;
        }

        // 6.由于head并没有处理指向，这里指向null
        head.next = null;

        // 7.返回next作为返回值
        return next;
    }

好吧，我承认我的第一次解题思路是根据自己的感觉乱试出来的，有种情窦初开，小鹿乱撞的感觉，一共用了8步。但是不管怎么样结果如期而至。

反思&纠错

首先表扬下自己，做了异常情况的判断，即判断了null节点和只有一个节点的情况

// 0.判断链表为空或者只有一个元素，无需反转
if(head == null || head.next == null){
   return head;
}

代码撸完后，感觉并不对，似乎走了不少弯路。一个这么简单的逻辑怎么可能写这么多行代码！这么多步骤！

然后...陷入沉思了...

第一个问题，我很快发现了，既然while循环有判断退出循环，我为什么还要判断在循环中break呢？

当时我是这样思考的：

不断挪动指针，next是最后一个节点并返回，如果不加if判断直接break，由于next = temp，因此next永远都是Null。那为什么不把pre作为返回值呢？迅速我改了一版，代码简洁多了。

 public static ListNode reverseList(ListNode head) {
        // 0.判断链表为空或者只有一个元素，无需反转
        if(head == null || head.next == null){
            return head;
        }


        ListNode pre = head;
        ListNode next = pre.next;
        ListNode temp;

        while(next != null){
            // 1.因为节点的next将指向前一个节点，临时缓存下一个节点
            temp = next.next;

            // 2.指向前一个节点
            next.next = pre;

            // 3.将next作为pre
            pre = next;
            // 4.将temp作为next
            next = temp;
        }

        // 5.由于head并没有处理指向，这里指向null
        head.next = null;

        // 6.返回next作为返回值
        return pre;
    }

比起初版少了一步，但是总觉得第5步是多余的呢？似乎是可以在循环中统一处理，为什么最后要增加一个特殊处理呢？head.next = null。

存在即合理，但合理未必简洁。

为了让自己更清楚地看到指针变动的过程及变量的变化，我决定用图来模拟这段代码指针的动态变化过程：

脑空间不足，请理解我用图脑补...

4个节点的单链表：

图2：第一次循环，执行完第2步

图3：第二次循环，执行完第2步

图4：第三次循环，执行完第2步

图5：循环结束，执行完第5步

细心的你，肯定已经发现了非常蹩脚的地方，1->2这个指针一直以说不出来的不合理存在，并且需要在循环结束后手动清除。

又一次反思中...

我第一次pre从node1开始，假设我们将pre从null开始呢？

突然脑海里面想起来极客时间的《数据结构与算法之美》链表中的一节讲到了一个概念:哨兵。

翻书中...

哨兵解决的是国家间的边界问题。似乎有那么点意思。尝试着将pre从null开始，next从node1开始呢？

噼里啪啦，重新修改代码中:

public static ListNode reverseList(ListNode head) {
        // 0.判断链表为空或者只有一个元素，无需反转
        if(head == null || head.next == null){
            return head;
        }

        ListNode pre = null;
        ListNode next = head;
        ListNode temp;

        while(next != null){
            // 1.因为节点的next将指向前一个节点，临时缓存下一个节点
            temp = next.next;

            // 2.指向前一个节点
            next.next = pre;

            // 3.将next作为pre
            pre = next;
            // 4.将temp作为next
            next = temp;
        }

        // 5.返回next作为返回值
        return pre;
    }

代码从原来的8步减少到了6步，减少了这两步代码，确实是自己走过的弯路。

似乎代码没有可以再继续优化的空间了，这几行代码也是自己对动态规划类问题的初识。

写在最后

链表的概念很容易理解，但是算法实现时，却往往由于指针的挪动，带来一定的复杂度。极容易烧脑，也可能脑裂，哈哈哈哈~，但也有诀窍。

你也可以按照我的思路来尝试解决问题。

• 第一步先按照自己的思路去实现
• 第二步找到自己认为不合理的点
• 优化问题，总结

比如我的这个总结：

1. 返回链表的节点可以以最后节点的前序节点，避开循环中再次判断break
2. 可以在处理的前序节点（也可以末尾节点）作为一个特殊的哨兵，减少冗余代码
3. 对于处理的临界点一定要仔细考虑，避免异常情况出现。

算法还是很有意思，我们在算法的海洋里再会！

我是公众号「面试怪圈」的kazz，喜欢我的原创，可以关注我，点个「在看」和「收藏」是对我最大的支持和鼓励！！！

欢迎到面试怪圈官网下载各种免费的学习资料：我的文章分享_java面试题_学习资料_基础知识点_项目实战以及算法等资料-面试怪圈