Java 中如何反转链表

简介

在 Java 编程中，链表是一种常见且重要的数据结构。反转链表是链表操作中的一个经典问题，在许多算法和实际应用场景中都有广泛的应用。本文将详细介绍在 Java 中反转链表的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并掌握这一技术。

基础概念

链表

链表是一种线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用（在单链表中）。与数组不同，链表的元素在内存中不是连续存储的，而是通过这些引用相互连接。

反转链表

反转链表就是将链表中节点的顺序颠倒过来。例如，对于链表 1 -> 2 -> 3 -> 4，反转后的链表为 4 -> 3 -> 2 -> 1。

使用方法

迭代法

迭代法是反转链表的一种常见方法。其基本思路是遍历链表，依次改变节点的引用方向。

// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class ReverseLinkedList {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public static void main(String[] args) {
        // 创建链表 1 -> 2 -> 3 -> 4
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        // 反转链表
        ListNode reversedHead = reverseList(head);

        // 打印反转后的链表
        while (reversedHead != null) {
            System.out.print(reversedHead.val + " ");
            reversedHead = reversedHead.next;
        }
    }
}

递归法

递归法通过递归地反转链表的后续部分，然后将当前节点插入到反转后的链表末尾。

// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class ReverseLinkedListRecursive {
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    public static void main(String[] args) {
        // 创建链表 1 -> 2 -> 3 -> 4
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        // 反转链表
        ListNode reversedHead = reverseList(head);

        // 打印反转后的链表
        while (reversedHead != null) {
            System.out.print(reversedHead.val + " ");
            reversedHead = reversedHead.next;
        }
    }
}

常见实践

处理空链表

在反转链表之前，需要检查链表是否为空。如果链表为空，直接返回 null。

if (head == null) {
    return null;
}

处理只有一个节点的链表

如果链表只有一个节点，反转后的链表仍然是该节点，直接返回该节点。

if (head.next == null) {
    return head;
}

最佳实践

选择合适的方法

迭代法的空间复杂度为 $O(1)$，时间复杂度为 $O(n)$，适合处理大规模链表。递归法的空间复杂度为 $O(n)$，因为递归调用栈的深度为 $n$，适合处理小规模链表或在需要递归思路的场景中使用。

代码可读性和可维护性

在编写代码时，要注意变量命名的清晰性和代码结构的合理性，提高代码的可读性和可维护性。

小结

本文介绍了在 Java 中反转链表的基础概念、使用方法（迭代法和递归法）、常见实践和最佳实践。迭代法和递归法各有优缺点，在实际应用中需要根据链表的规模和具体需求选择合适的方法。通过掌握这些方法，读者可以更好地处理链表相关的问题。

参考资料

《算法导论》
Java 官方文档
LeetCode 相关题目及题解