题解:反转链表
这道题目要求我们将一个单链表进行反转,返回反转后的链表。链表的反转可以通过 迭代 和 递归 两种方法来实现。下面我们将详细解释这两种方法,并通过例子演示每一步的变化过程。
方法一:迭代法
思路:
- 我们用三个指针来完成链表的反转:
prev
表示前一个节点,curr
表示当前节点,next
表示下一个节点。 - 通过不断将当前节点的
next
指针指向prev
,实现链表的逐步反转。
迭代的步骤:
- 初始化
prev = null
和curr = head
,然后开始遍历链表。 - 在每次迭代中,先用
next
保存curr.next
,避免链表断开。 - 将
curr.next
指向prev
,反转当前节点的指向。 - 将
prev
移动到curr
,然后将curr
移动到next
,继续下一次迭代。 - 当
curr
为null
时,链表反转完成,prev
就是新的头节点。
代码实现:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // 保存下一个节点
curr.next = prev; // 反转当前节点的指向
prev = curr; // 将 prev 前移
curr = next; // 将 curr 前移
}
return prev; // prev 成为新链表的头节点
}
}
例子演示:
输入:head = [1,2,3,4,5]
-
初始状态:
prev = null curr = 1 -> 2 -> 3 -> 4 -> 5
-
第一步:
next = 2 -> 3 -> 4 -> 5 curr.next = prev // 1 -> null prev = 1 -> null curr = 2 -> 3 -> 4 -> 5
-
第二步:
next = 3 -> 4 -> 5 curr.next = prev // 2 -> 1 -> null prev = 2 -> 1 -> null curr = 3 -> 4 -> 5
-
第三步:
next = 4 -> 5 curr.next = prev // 3 -> 2 -> 1 -> null prev = 3 -> 2 -> 1 -> null curr = 4 -> 5
-
第四步:
next = 5 curr.next = prev // 4 -> 3 -> 2 -> 1 -> null prev = 4 -> 3 -> 2 -> 1 -> null curr = 5
-
第五步:
next = null curr.next = prev // 5 -> 4 -> 3 -> 2 -> 1 -> null prev = 5 -> 4 -> 3 -> 2 -> 1 -> null curr = null
输出:[5, 4, 3, 2, 1]
复杂度分析:
- 时间复杂度:O(n),其中
n
是链表的节点数。我们只遍历了链表一次。 - 空间复杂度:O(1),只用了常数级别的额外空间。
方法二:递归法
思路:
- 我们递归地反转链表的后续部分,直到最后一个节点成为新的头节点。
- 每次递归返回时,将当前节点的下一个节点的
next
指向自己,同时将自己的next
置为空,完成反转。
递归步骤:
- 如果
head
为null
或者head.next
为null
,直接返回head
作为新的头节点(即递归的终止条件)。 - 递归反转剩余的链表。
- 将当前节点的下一个节点的
next
指向自己,同时将自己的next
置为空。 - 返回新的头节点。
代码实现:
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head; // 递归终止条件
ListNode newHead = reverseList(head.next); // 反转后续链表
head.next.next = head; // 将后面的节点指向自己
head.next = null; // 断开当前节点与后续的连接
return newHead; // 返回新的头节点
}
}
例子演示:
输入:head = [1,2,3,4,5]
-
初始递归:
reverseList(1)
递归调用reverseList(2)
。
-
递归到最后一个节点:
reverseList(5)
返回5
作为新头节点。
-
逐步反转链表:
-
reverseList(4)
:head = 4 -> 5 反转后 5 -> 4 head.next.next = 4 head.next = null // 4 -> null 返回 5 -> 4 -> null
-
reverseList(3)
:head = 3 -> 4 -> null 反转后 5 -> 4 -> 3 head.next.next = 3 head.next = null 返回 5 -> 4 -> 3 -> null
-
reverseList(2)
:head = 2 -> 3 -> null 反转后 5 -> 4 -> 3 -> 2 head.next.next = 2 head.next = null 返回 5 -> 4 -> 3 -> 2 -> null
-
reverseList(1)
:head = 1 -> 2 -> null 反转后 5 -> 4 -> 3 -> 2 -> 1 head.next.next = 1 head.next = null 返回 5 -> 4 -> 3 -> 2 -> 1 -> null
-
输出:[5, 4, 3, 2, 1]
复杂度分析:
- 时间复杂度:O(n),其中
n
是链表的节点数。递归过程中每个节点只处理一次。 - 空间复杂度:O(n),递归调用的栈深度为
n
。
总结:
- 迭代法:通过三个指针逐步反转链表,时间和空间复杂度都为 O(n) 和 O(1),适合在空间要求较严格的场景下使用。
- 递归法:利用函数调用栈进行递归,代码简洁直观,但需要 O(n) 的额外空间。