一、题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
二、解题思路
反转单链表的经典做法是使用三个指针：prev、current 和 next。初始时，prev 指向 null，current 指向 head。遍历链表，在遍历过程中，我们需要做以下操作：
- 使用 next 临时保存 current 的下一个节点，防止链表丢失。
- 将 current 的 next 指向 prev，实现局部反转。
- 将 prev 移动到 current，current 移动到 next。
当 current 为 null 时，说明已经遍历到链表尾部，此时 prev 就是新的头节点。
三、具体代码
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null; // 反转后的链表头节点ListNode current = head; // 当前遍历的节点ListNode next = null; // 临时保存下一个节点while (current != null) {next = current.next; // 保存下一个节点current.next = prev; // 反转当前节点prev = current; // prev 移动到当前节点current = next; // 当前节点移动到下一个节点}return prev; // prev 是新的头节点}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 该算法通过一个 while 循环遍历整个链表，每遍历一个节点，就进行一次反转操作。
- 链表中的每个节点都只被访问一次，因此，算法的时间复杂度是 O(n)，其中 n 是链表的长度。
2. 空间复杂度
- 在这个算法中，使用了三个额外的指针（prev、current、next）来保存节点信息，这些指针是固定数量的，不随输入链表的大小而改变。
- 除了输入的链表本身外，没有使用额外的存储空间，如数组或哈希表等。
- 因此，算法的空间复杂度是 O(1)，表示使用了常数级别的额外空间。
五、总结知识点
-
链表（Linked List）：链表是一种常见的基础数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针域。
-
节点（ListNode）：节点是链表的基本单元，通常包含数据和指向下一个节点的引用。
-
指针（Pointer）：在 Java 中，引用（Reference）类似于 C/C++ 中的指针，用于指向内存中的对象或变量。
-
迭代（Iteration）：使用
while循环来遍历链表，这是迭代的一种形式。 -
三指针法（Three Pointers）：使用三个指针（prev, current, next）来反转链表，这是反转链表时的常用技巧。
-
临时变量（Temporary Variable）：使用临时变量
next来保存当前节点的下一个节点，防止在修改指针时丢失链表的后续部分。 -
指针操作（Pointer Manipulation）：代码中涉及了指针的赋值操作，如
current.next = prev;用于反转节点的指向。 -
边界条件处理（Boundary Condition Handling）：当
current为null时，表示链表已经遍历完毕，此时prev指向新的头节点。 -
递归与迭代（Recursion vs Iteration）：尽管本题使用迭代方法实现链表反转，但也可以使用递归来实现相同的功能。
-
函数定义（Function Definition）：
reverseList是一个成员函数，它接受一个链表的头节点head作为参数，并返回反转后的链表的头节点。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。