单链表反转是常见的面试题目之一，下面是关于如何反转一个单链表的思路、时间和空间复杂度分析以及完整的 Java 代码实现。

思路

单链表反转的关键在于改变每个节点的指向，使得原来指向下一个节点的指针指向前一个节点。为了做到这一点，我们可以通过迭代的方式来逐个调整节点的指针。

具体步骤：

1. 初始化三个指针：
   • prev：指向前一个节点，初始化为 null。
   • curr：指向当前节点，初始化为链表的头节点。
   • next：指向当前节点的下一个节点，初始化为 null。
2. 遍历链表：
   • 每次保存 curr 的下一个节点 (next = curr.next)。
   • 将当前节点的 next 指向 prev（反转指向）。
   • 将 prev 移动到 curr，将 curr 移动到 next，继续遍历。
3. 完成遍历后，prev 会指向新链表的头节点。

时间复杂度

• 时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历一次整个链表。
• 空间复杂度：O(1)，我们只用了常数空间来存储指针，不需要额外的空间。

Java 完整代码实现

public class Solution {

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

    // 反转链表的函数
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;  // 初始化前一个节点为null
        ListNode curr = head;  // 当前节点从头节点开始
        
        while (curr != null) {
            ListNode next = curr.next;  // 保存下一个节点
            curr.next = prev;  // 反转当前节点的指针
            prev = curr;  // 前一个节点移动到当前节点
            curr = next;  // 当前节点移动到下一个节点
        }
        
        return prev;  // prev最终会是新的头节点
    }

    // 打印链表的辅助函数
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // 创建一个链表：1 -> 2 -> 3 -> 4 -> 5 -> null
        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);
        
        // 打印原链表
        System.out.println("Original list:");
        printList(head);
        
        // 反转链表
        ListNode reversedHead = reverseList(head);
        
        // 打印反转后的链表
        System.out.println("Reversed list:");
        printList(reversedHead);
    }
}

代码解析：

1. ListNode 类：定义了一个链表节点，每个节点包含一个整数值 val 和指向下一个节点的指针 next。
2. reverseList 方法：用于反转链表。通过 prev、curr 和 next 三个指针来实现链表的反转。
3. printList 方法：用于打印链表，用来测试链表是否正确反转。
4. main 方法：在 main 方法中，创建一个示例链表，反转它并打印反转前后的链表。

测试示例：

输入链表：
1 -> 2 -> 3 -> 4 -> 5 -> null

输出链表：
5 -> 4 -> 3 -> 2 -> 1 -> null

总结：

• 时间复杂度：O(n) —— 需要遍历一次链表。
• 空间复杂度：O(1) —— 只使用了常量级别的额外空间。

这个问题考察了基本的链表操作和指针的使用，掌握这个技巧对于后续涉及链表的题目有很大帮助。