一、定义链表

这里定义带哨兵的链表

package linkedlist;

// 反转链表的五种方式
public class ReverseLinkedList {
    private final Node head = new Node(null, null);

    // 快速填充链表
    public void fill() {
        Node n5 = new Node(5, null);
        Node n4 = new Node(4, n5);
        Node n3 = new Node(3, n4);
        Node n2 = new Node(2, n3);
        head.next = new Node(1, n2);
    }

    // 打印链表
    public void display() {
        Node p = head.next;
        while (p != null) {
            System.out.print(p.value + " -> ");
            p = p.next;
        }
    }

    private static class Node {
        private final Object value;
        private Node next;

        public Node(Object value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ReverseLinkedList linkedList = new ReverseLinkedList();
        linkedList.fill();
        linkedList.display();
    }
}

二、反转链表

2.1 方式一

创建一个新的链表，依次遍历老的链表获取的元素插入到新链表首位

public ReverseLinkedList reverse1() {
    // 创建新的链表
    ReverseLinkedList newList = new ReverseLinkedList();
    // 遍历当前链表
    Node p = head.next;
    while (p != null) {
        // 首插法
        newList.head.next = new Node(p.value, newList.head.next);
        p = p.next;
    }
    return newList;
}

下面用图解释一下newList.head.next = new Node(p.value, newList.head.next);是如何实现将元素插入头部

对于 new Node(p.value, newList.head.next) 图示如下

最后 newList.head.next = new

2.2 方式二

方式一的缺点就是每一个节点都需要重新创建，空间复杂度较高。

因此方式二对这点进行优化，其基本思路依然是遍历，只不过是依次移除原链表的每个节点并将其插入到新链表的头部，下面是将一个 node 节点添加到链表头部

public void addFirst(Node node) {
    node.next = head.next;
    head.next = node;
}

下面是移除链表头部元素

public Node removeFirst() {
    // 保存第一个元素
    Node p = head.next;
    // 判空
    if (p != null) {
        // 移除第一个元素
        head.next = head.next.next;
    }
    return p;
}

因此方式二的方式如下

public ReverseLinkedList reverse2() {
    ReverseLinkedList newList = new ReverseLinkedList();
    // 依次移除链表元素
    Node node = removeFirst();
    while (node != null) {
        newList.addFirst(node);
        node = removeFirst();
    }

    return newList;
}

2.3 方式三

方式二依然是创建了新的链表对象，只不过没有创建新的节点对象，有没有一种方式是在原链表的基础上直接进行反转？首先我们实现通过递归方式找到链表的最后一个节点

public void test() {
    System.out.println(recursion(head.next).value);
}

private Node recursion(Node node) {
    if (node == null || node.next == null) {
        return node; // 最后一个节点
    }
    return recursion(node.next);
}

递归调用实例图如下：

上述递归我们发现

当 node = 4 时，此时 node -> 4; node.next -> 5，不看其他节点只将 5 -> 4，那么此刻的指向时 5 -> 4; 4 -> 5

当 node = 3 时，此时 node -> 3; node.next -> 4，不看其他节点只将 4 -> 3，那么此刻的指向时 5 -> 4; 4 -> 3; 3 -> 4

当 node = 2 时，此时 node -> 2; node.next -> 3，不看其他节点只将 3 -> 2，那么此刻的指向时 5 -> 4; 4 -> 3; 3 -> 2; 2 -> 3

当 node = 1 时，此时 node -> 1; node.next -> 2，不看其他节点只将 2 -> 1，那么此刻的指向时 5 -> 4; 4 -> 3; 3 -> 2; 2 -> 1; 1 -> 2

看起来似乎是反转了链表，但细心的同学或许发现问题所在，就是每层递归结束后的节点指向存在循环引用的风险，且最后一次递归应该指向 null，所以我们在交换指针指向时多做一步，例如

当 node = 4，我们需要将 5 -> 4 同时将 4 -> null 即可，代码如下

private Node recursion(Node node) {
    if (node == null || node.next == null) {
        return node; // 最后一个节点
    }
    Node recursion = recursion(node.next);
    node.next.next = node;
    node.next = null;
    return recursion;
}

ReverseLinkedList 作为对 Node 的封装同时携带一个哨兵节点，那么我们只需要在方法结束获取返回值时，将 head 指向该返回值即可，因此方法三代码如下：

public void reverse3() {
    head.next = recursion(head.next);
}

2.4 方法四

其思路和方法二类似，区别在于该方法是在原链表上面直接操作指向实现反转，思路如下：

step-1: 定义三个指针，n1 始终指向链表第一个节点，o1 初始状态指向链表第一个节点，o2 始终指向 o1 的下一个节点

step-2: 断开 o2 指向的节点，即o1.next = o2.next

step-3: 将 o2 链入到链表头部，即o2.next = n1

step-4: 此时已完成1、2节点的反转，下面需要让 n1 和 o2 回归原本语义，即 n1 始终指向链表头部，那么o1 = o2；o2 始终指向 o1 的下一个节点，那么o2 = o1.next

step-5: 重复 step-2 直到 o2 = null

代码实现如下：

public void reverse4() {
    // step-1: 定义三个指针，n1 始终指向链表第一个节点，o1 初始状态指向链表第一个节点，o2 始终指向 o1 的下一个节点
    Node n1 = head.next;
    Node o1 = head.next;
    if (o1 == null) {
        // 空链表
        return;
    }
    Node o2 = o1.next;
    // step-5: 重复 step-2 直到 o2 = null
    while (o2 != null) {
        // step-2: 断开 o2 指向的节点
        o1.next = o2.next;
        // step-3: 将 o2 链入到链表头部
        o2.next = n1;
        // step-4: 此时已完成1、2节点的反转，下面需要让 n1 和 o2 回归原本语义
        n1 = o2;
        o2 = o1.next;
    }
    // 改变 head 指向
    head.next = n1;
}

2.5 方法五

方法五是对方法二的重构，思路就是循环老链表每个节点依次插入到新的链表头部，区别在于方法二是面向对象，而方法五是面向过程，相较于此代码量和可读性将进一步提高，思路如下

step-1: 定义两个指针，o1 始终指向老链表头部，n1 始终指向新链表头部，初始为 null

step-2: 先定义一个辅助节点 o2 指向 o1 的下一个节点，然后将 o1 指向的节点链入 n1 新链表的头部。o2 的作用是让 o1 能回归原本的语言（当然用 head 回去也是一样的，只不过要平凡动 head）

step-3: n1、o1 归位，即 n1 始终指向新链表头部，o1 始终指向老链表头部，这里 o1 需要借助 o2 才能归为

step-4: 如果 o1 不指向 null 则回到 step-2，否则结束