链表反转的 Java 实现

1. 简介

本教程中，我们将用 Java 实现两种链表反转算法。

2. 链表数据结构

链表是一种线性数据结构，其中每个元素通过指针来决定顺序。每个链表元素包含一个数据字段用于存储数据，以及一个指针字段指向下一个元素。此外，我们通常使用一个 head 指针来指向链表的第一个元素：

当我们将链表反转后，head 指针将指向原链表的最后一个元素，同时每个元素的指针将指向前一个元素：

在 Java 中，我们有 LinkedList 类来提供 List 和 Deque 接口的双向链表实现。不过在本教程中，我们将使用普通的单向链表结构。

我们先定义一个 ListNode 类来表示链表中的元素：

public class ListNode {

    private int data;
    private ListNode next;

    ListNode(int data) {
        this.data = data;
        this.next = null;
    }

   // 标准的 getter 和 setter
}

ListNode 类有两个字段：

• 一个整型值，表示节点存储的数据
• 一个指向下一个节点的引用

链表可以包含多个 ListNode 对象。例如，我们可以通过循环构造如上图所示的链表：

ListNode constructLinkedList() {
    ListNode head = null;
    ListNode tail = null;
    for (int i = 1; i <= 5; i++) {
        ListNode node = new ListNode(i);
        if (head == null) {
            head = node;
        } else {
            tail.setNext(node);
        }
        tail = node;
    }
    return head;
}

3. 迭代算法实现

接下来我们用 Java 实现迭代算法：

ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextElement = current.getNext();
        current.setNext(previous);
        previous = current;
        current = nextElement;
    }
    return previous;
}

在这个迭代算法中，我们使用两个 ListNode 变量 previous 和 current 来表示链表中的相邻两个节点。每次迭代中，我们将这两个节点的指向反转，然后向前移动。

最终，current 指针会变为 null，而 previous 指针则会指向原链表的最后一个节点。因此，previous 也是反转后链表的新头节点，我们将其返回。

可以通过一个简单的单元测试来验证这个迭代实现：

@Test
void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {
    ListNode head = constructLinkedList();
    ListNode node = head;
    for (int i = 1; i <= 5; i++) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
 
    LinkedListReversal reversal = new LinkedListReversal();
    node = reversal.reverseList(head);
 
    for (int i = 5; i >= 1; i--) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
}

在这个测试中，我们首先构造了一个包含五个节点的链表，并验证每个节点的数据是否正确。然后调用迭代函数进行反转，最后检查反转后的链表是否符合预期。

4. 递归算法实现

现在我们来实现递归算法：

ListNode reverseListRecursive(ListNode head) {
    if (head == null) {
        return null;
    }
    if (head.getNext() == null) {
        return head;
    }
    ListNode node = reverseListRecursive(head.getNext());
    head.getNext().setNext(head);
    head.setNext(null);
    return node;
}

在 reverseListRecursive 方法中，我们递归访问链表中的每个节点，直到到达最后一个节点。这个节点将成为反转后链表的新头节点。同时，我们将当前访问的节点追加到已部分反转的链表末尾。

同样，我们可以用一个简单的单元测试来验证递归实现：

@Test
void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {
    ListNode head = constructLinkedList();
    ListNode node = head;
    for (int i = 1; i <= 5; i++) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
 
    LinkedListReversal reversal = new LinkedListReversal();
    node = reversal.reverseListRecursive(head);
 
    for (int i = 5; i >= 1; i--) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
}

5. 总结

在本教程中，我们实现了两种链表反转算法。一如既往，本文的完整源码可以在 GitHub 上找到。

✅ 链表反转是面试中的高频题，掌握迭代和递归两种写法对理解指针操作非常有帮助
⚠️ 递归写法虽然简洁，但要注意栈溢出风险，尤其在链表较长时
❌ 不要搞混 head 和 tail 指针的含义，否则容易写出死循环或空指针异常的代码