1. 前言

相对于各种复杂的二叉树（例如平衡二叉树、完美二叉树），单链表的数据结构简单，只涉及到一个值和指针的操作，所以面试中经常会出现需要手写单链表的算法题。反转链表应该是单链表中考察频率最高的题目，题目看起来比较简单，但是因为涉及的指针操作较多，要实现一遍 bug free 也不太容易。

2. 反转链表

2.1 算法实现

面试官提问：如何反转一个单链表？手写实现一下源码。

题目解析：

反转链表是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/reverse-linked-list/。

反转链表有多种解法：

（1）比较暴力（brute force）的方法是将链表的值放入一个有序数组，然后倒序从数组中取值，重新放入原有的链表。优点是算法简单，缺点是需要使用额外的数组空间，并且面试官一般不会接受这种不够优雅的算法；
（2）递归算法，递归本质上也会使用额外的栈空间（stack memory），优点是算法简洁，一般来说面试官也能接受递归；
（3）循环算法，使用多个指针在一次循环里改变链表顺序，不会使用额外的空间，时间复杂度是O（N），这里只介绍这个方法。

循环算法中，我们需要借助三个指针，before 指针指向上一个操作节点，head 指针指向当前操作节点，next 指针指向下一个操作节点。算法可以拆分为两个步骤：

（1）对于空链表以及只有单个节点的链表，直接返回链表本身，不需要进行反转；
（2）对于普通链表，通过循环三个指针的操作实现链表反转，我们使用Java实现反转算法。

示例：

class Solution {
    public ListNode reverseList(ListNode head) {
        //1. 判断边界条件
        if(head == null || head.next == null){
            return head;
        }
        //2. 迭代反转
        ListNode dummy = head;
        ListNode next, before = null;
        while(head != null){
            //3.1 反转
            next = head.next;
            head.next = before;
          	//3.2 往后移动一位
            before = head;
            head = next;
        }
        return before;
    }
}

为了校验我们的算法是否有效，假设一个包含5个节点的链表，算法模拟的过程如下：

最开始给定的原始链表的结构如下，其中黄色部分代表指针，蓝色部分代表具体值：

经过3.1步骤之后，链表的第一个节点被反转，指向了before节点，此时before节点还是Null：

然后经过3.2步骤后，我们把before、head、next的值都往后移动一位，第一个节点就完全实现了反转：

接下来，我们重复上述步骤，直到 head 节点指向 Null ，即完成了整个链表的反转，返回 before 节点就是新链表的头节点。

2.2 细节考察

分析算法的时间复杂度和空间复杂度：上述循环算法，因为没有使用递归，没有使用额外的普通数组辅助存储，只是使用了两个临时变量，所以空间复杂度为O（1）。因为通过单循环顺序遍历链表，所以时间复杂度为O（N）。

对于节点数量少于两个的链表，需要提前返回原始链表，防止 NullPointerException空指针异常。

3. 小结

本章节介绍了单链表中最经典的反转链表问题，候选人从编写算法源码、通过小规模测试样例验证算法是否符合预期以及分析算法的时间和空间复杂度三个纬度入手，给出面试官满意的答案。