文章目录

1. 1. 参考

「反转单向链」问题是面试时最常见的一道题了，我们一起来好好地攻克它。 首先我们得有一条单向链吧，没错，先知道单向链是个什么东东，怎么造出来。 先来看下单向链的定义：是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过头部开始，依序往下读取。 通俗一点地说，就是方向单一，有头有尾，每个节点都有惟一的一条next指针，指向它下一个节点，当然，尾部节点的next指针，指向的是空。 要解决反转的问题，就需要先准备好一条单向链，先定义一个单向链的类，其实，实践中来说，只需要定义好一个节点类就行，因为有了一个头节点，只要它身后挂有其他节点，就已经隐含了一条单向链。 下面我将先Java语言来实现，其后会用其他的语言重写，大家可以参考。

单向链的节点类

public class Node <T> {
    public T value;
    public Node next;
}

这里我们定义类的时候会声明一个类型为T，用于指定节点上的值的类型。 接着，我们先整理下思路后，再开始写代码，个人心得是不要急忙地开工写，一定要先把思路捋清后才动手，这样不会陷入代码的枝蔓里。不多说，这道题的解决根本是怎么把节点间的指向方向调转一下，而且是每个节点都需要走到，才能最终得到我们想要结果。

设想一下，现有一个链条如下： A -> B -> C -> D -> null 我们想要的结果是 D -> C -> B -> A -> null 看似麻烦，其实是可以换向思维，把问题转成这样： null <- A <- B <- C <- D 嗯，这样的话，我们就可以对原链条上的每个节点做一次迭代，直到链尾。 因为不是数组，没有下标作为判断索引，可以采用while语句来实现，那条件是什么呢？ 显示是走到链尾了，意思也是走到了最后一个节点。而最后一个节点的定义是它的next指向了null。 所以可以这样while (node.next != null)，嗯，看起来不错，那怎么切换到下一个节点呢？毕竟，现在手头只有一个头节点，那么可以假定当前的节点为current变量，这个变量是需要定义在while语句外的，并且初始是设定为头节点head，这个head是通过参数传入方法内，并且方法的返回值也是一个节点（因为有了这个新的头节点，就能拉起一条单向链了）。这样：

public Node reverse(Node node) {
    Node current = head;
    while (current.next != null) {
        ...
    }
}

显然，最后要返回的节点从示例上来看，就是节点D，我们先定义一个变量，用于作最终的返回对象。

Node result = null; // 初始值为null

由定义可知，每个节点都有一个next指向到下一个节点，对比两条单向链，可以发现，我们其实是需要知道每个节点的上一个节点（previous）是谁，才能把指向方向转变，从而指向为next。 因为我们是需要一个变量来存储迭代过程中每个节点的上一个节点：

Node previous = null; //初始值为null，因为头节点的`previous`是`null`。

现在我们有了如下代码：

public Node reverse(Node node) {
    Node current = head;
    Node result = null; // 初始值为null
    Node previous = null; //初始值为null，因为头节点的`previous`是`null`。
    while (current.next != null) {
        ...
    }
}

那么循环体内怎么写呢？这里才能整个题目最重要也是最容易出错的地方。 首先，我们第一次进入循环，是处于第一个节点的位置上。即current是节点A，我们可以通过current.next拿到它的下一个节点B的引用。因为我们接下来会把next指向到它的前一个节点上，即循环体外的previous变量上，而一旦这样做了后，我们就会失去节点B的引用，再也拿不到。所以我们一定要在修改当前节点的next属性前，先把其后的节点的引用保存到一个临时变量，暂命名为next，类型也是Node。现在代码如下：

public Node reverse(Node node) {
    Node current = head;
    Node result = null; // 初始值为null
    Node previous = null; //初始值为null，因为头节点的`previous`是`null`。
    while (current.next != null) {
        Node next = current.next;
        ...
    }
}

我们要迭代走完所有节点，就需要把当前节点指向到下一个节点，因此这样，在循环体的最后一行加上：

current = next;

整体如下：

public Node reverse(Node node) {
    Node current = head;
    Node result = null; // 初始值为null
    Node previous = null; //初始值为null，因为头节点的`previous`是`null`。
    while (current.next != null) {
        Node next = current.next;
        ...
        current = next;
    }
}

接着就是转换箭头了，可以这样：

current.next = previous;

整体如下：

public Node reverse(Node node) {
    Node current = head;
    Node result = null; // 初始值为null
    Node previous = null; //初始值为null，因为头节点的`previous`是`null`。
    while (current.next != null) {
        Node next = current.next;        
        current.next = previous;
        ...
        current = next;
    }
}

这样就OK了吗？当然不是，细心的读者会发现，一个迭代走下来，所有的节点的next都指向了一个previous，而这个变量从头到尾都是null。嗯，有问题。 怎么解决？那就是在每次的迭代结束前，把previous变量更新成当前的节点，这样，在下次进入循环体时，previous才是当前节点的上一个节点。

最后再加上要返回的节点，如下：

public Node reverse(Node node) {
    Node current = head;
    Node result = null; // 初始值为null
    Node previous = null; //初始值为null，因为头节点的`previous`是`null`。
    while (current.next != null) {
        Node next = current.next;        
        current.next = previous;
        previous = current;
        current = next;
    }
    return result;
}

问题是返回的结果永远都是null，因为result变量从头到尾就没有发生过改变。 应该怎么改变呢？我们最终要的只是最后一个节点的引用就行，所以，可以在最后一次迭代（即current.next为空）时，把最后一个节点赋予result变量即可。

result = current;

这条语句应该放在什么位置呢？嗯，得放在current变量被修改引用之前，是否还可以再前置点？既然只要在最后一次迭代时，对result赋值，完全可以前置到Node next = current.next之后就行。如下：

Node next = current.next;
result = current;
current.next = previous;
previous = current;
current = next;

好的，So far so good.，一切都显得美好。整体如下：

public Node reverse(Node node) {
    Node current = head;
    Node result = null; // 初始值为null
    Node previous = null; //初始值为null，因为头节点的`previous`是`null`。
    while (current.next != null) {
        Node next = current.next;  
        result = current;      
        current.next = previous;
        previous = current;
        current = next;
    }
    return result;
}

再回顾下代码，除了输入得加上校验（有面试官对这里很看重，大家谨记）外，发现最后一个节点实际上是不能遍历到（因为它的next为空，不满足循环条件），那么我们就没法在循环体内得到最后一个节点的引用并赋值给result变量，此时，方法返回的是倒数第二个节点的引用，还得改。 我们把while条件放宽到囊括住最后一个节点，如：while (current != null)。前面已经说过，我们只需要在最后一次迭代时，对result赋值为当前节点即可，无需每次都要这么操作，可优化为

if (next == null) {
    result = current;
}

大功告成，整体方法的代码如下：

public Node reverse(Node head) {
    if (head == null) {
        return null;
    }
    Node result = null;
    Node current = head;
    Node previous = null;
    while (current != null) {
        Node next = current.next;
        if (next == null) {
            result = current;
        }
        current.next = previous;
        previous = current;
        current = next;
    }
    return result;
}

完整的代码 NodeLink.java Node.java

总之，大家一定要把反转的思路理清，千万不要死记硬背，否则，临场的紧张就特别容易把整个人弄懵（多个变量来回的修改引用，把自己绕晕），心态打乱后就没法好好地手写出代码。 希望对自己，对他人都有所帮助吧。

参考

• wiki