Java 算法篇-深入了解单链表的反转（实现：用 5 种方式来具体实现）

在数据结构中，单链表是一种重要的线性表形式，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。单链表的反转是一个经典问题，涉及到将链表的方向颠倒，从而改变节点的连接顺序。本文将介绍五种不同方式来实现单链表的反转，并提供相应的 Java 代码示例。

1. 迭代法

最常见的反转单链表的方法是使用迭代。我们使用三个指针来遍历链表：prev、current 和 next。

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode next = current.next; // 保存下一个节点
        current.next = prev; // 反转当前节点指向
        prev = current; // 移动 prev 和 current 进行下一次迭代
        current = next;
    }
    return prev; // prev 将是新的头节点
}

2. 递归法

反转单链表还可以使用递归的方法。这个方法的关键在于递归调用会反转后面的子链表。

public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head; // 到达链表尾部或空链表
    }
    ListNode newHead = reverseListRecursive(head.next); // 递归反转后面的链表
    head.next.next = head; // 将当前节点与后续节点反转
    head.next = null; // 当前节点的下一个指针置为 null
    return newHead; // 返回新的头节点
}

3. 栈法

我们可以使用栈来辅助反转链表，因为栈是后进先出（LIFO）结构。

import java.util.Stack;

public ListNode reverseListUsingStack(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    ListNode current = head;

    while (current != null) {
        stack.push(current);
        current = current.next;
    }

    if (stack.isEmpty()) {
        return null;
    }

    ListNode newHead = stack.pop();
    current = newHead;

    while (!stack.isEmpty()) {
        current.next = stack.pop();
        current = current.next;
    }
    current.next = null; // 末尾节点指向 null
    return newHead;
}

4. 优化的迭代法

在某些情况下，我们可以使用双指针来反转链表，同时避免使用额外空间。

public ListNode reverseListOptimized(ListNode head) {
    if (head == null) return null;

    ListNode newHead = null;

    while (head != null) {
        ListNode next = head.next; // 保存下一个节点
        head.next = newHead; // 将当前节点的指针指向新的表头
        newHead = head; // 更新新的表头为当前节点
        head = next; // 移动到下一个节点
    }
    return newHead;
}

5. Morris 反转法

Morris 方法是一种空间复杂度为 O(1) 的算法，通过改变节点的指向来反转链表。

public ListNode reverseListMorris(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode nextTemp = current.next;
        current.next = prev; // 反转指向
        prev = current; // 移动指针
        current = nextTemp; // 移动到下一个节点
    }
    return prev; // 新的头节点
}

总结

本文介绍了五种不同的单链表反转的方法，包括迭代法、递归法、栈法、优化的迭代法以及 Morris 反转法。每种方法都有其独特的优缺点，开发者可以根据具体的场景选择适合的方法。在实际编码中，理解每种算法的时间复杂度和空间复杂度是十分重要的，这可以帮助选择出效率最高的实现方式。