9. 如何反转一个单链表？请使用迭代和递归两种方法实现。

PangHu大约 3 分钟

反转单链表是一个经典的算法问题。在单链表中，每个节点包含一个数据部分和一个指向下一个节点的指针。反转单链表就是将链表中的所有节点的指针方向反转，使链表的第一个节点变成最后一个节点，最后一个节点变成第一个节点。

一、链表节点的定义

首先，我们需要定义一个链表节点的类。

java复制代码class ListNode {
    int val;
    ListNode next;

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

二、迭代方法反转单链表

1. 基本思路

迭代方法反转链表的基本思路是遍历链表，并逐个反转每个节点的指针方向。我们使用三个指针来实现这一过程：

prev：指向当前节点的前一个节点。
current：指向当前节点。
next：指向当前节点的下一个节点，用于临时存储，以便在反转指针后继续遍历。

2. 具体实现

java复制代码public class ReverseLinkedListIterative {

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

        while (current != null) {
            ListNode next = current.next; // 暂存当前节点的下一个节点
            current.next = prev;          // 反转当前节点的指针方向
            prev = current;               // 将 prev 移动到当前节点
            current = next;               // 将 current 移动到下一个节点
        }

        return prev; // 返回新的头节点
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode reversedHead = reverseList(head);

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

3. 时间复杂度

时间复杂度：O(n)，其中 n 是链表的节点数。每个节点被访问一次。
空间复杂度：O(1)，只使用了几个额外的指针，空间复杂度是常数级别。

三、递归方法反转单链表

1. 基本思路

递归方法反转链表的思路是从链表的尾部开始，将每个节点的 next 指针反转指向前一个节点，最终将链表头节点的 next 指向 null。递归的基本步骤如下：

将链表分为两部分：头节点和剩余部分。
递归地反转剩余部分。
将头节点的 next 指向 null，并将反转后的链表尾节点指向头节点。

2. 具体实现

public class ReverseLinkedListRecursive {

    public static ListNode reverseList(ListNode head) {
        // 基本情况：空链表或只有一个节点的链表
        if (head == null || head.next == null) {
            return head;
        }

        // 递归反转剩余的链表
        ListNode newHead = reverseList(head.next);

        // 将当前节点的下一个节点的 next 指针指向当前节点
        head.next.next = head;
        head.next = null; // 将当前节点的 next 指针设置为 null

        return newHead; // 返回新的头节点
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode reversedHead = reverseList(head);

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

3. 时间复杂度

时间复杂度：O(n)，其中 n 是链表的节点数。每个节点被访问一次。
空间复杂度：O(n)，由于递归调用的栈深度为 n，因此空间复杂度是 O(n)。

四、总结

迭代方法：使用三个指针遍历链表，逐步反转每个节点的指针方向，时间复杂度为 O(n)，空间复杂度为 O(1)。适用于大部分场景，特别是在内存资源有限的情况下。
递归方法：通过递归调用函数来反转链表，时间复杂度为 O(n)，空间复杂度为 O(n)。递归方法的实现比较简洁，但在链表长度较长时可能会导致栈溢出。

这两种方法各有优缺点，根据具体情况选择合适的实现方式。在实际开发中，迭代方法由于其空间效率更高，通常是更为推荐的选择。