15. 反转链表：反转一个单链表

反转一个单链表是一个常见的算法问题，可以通过迭代或递归两种方法来实现。在反转链表的过程中，需要改变每个节点的 next 指针，使其指向前一个节点，从而使链表的方向发生反转。

链表节点的定义

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

class ListNode {
    int val;
    ListNode next;

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

一、迭代法反转链表

1. 思路

使用三个指针来反转链表：

• prev 指向当前节点的前一个节点（初始为 null）。
• current 指向当前节点。
• next 用于暂时存储当前节点的下一个节点，以便在反转指针后继续遍历。

反转的步骤如下：

• 保存当前节点的下一个节点 next。
• 将当前节点的 next 指向前一个节点 prev。
• 将 prev 移动到当前节点，将 current 移动到下一个节点（即 next）。

2. 代码实现

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 指针指向 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)。适合理解链表的递归处理，但在实际应用中通常不如迭代法高效。

根据具体情况选择合适的反转链表方法。迭代法更适合实际开发，特别是在需要处理长链表时。