文章目录
题目
标题和出处
标题：反转链表
出处：206. 反转链表
难度
3 级
题目描述
要求
给你单链表的头结点 head \texttt{head} head，请你反转链表，并返回反转后的链表。
示例
示例 1：
输入：
head
=
[1,2,3,4,5]
\texttt{head = [1,2,3,4,5]}
head = [1,2,3,4,5]
输出：
[5,4,3,2,1]
\texttt{[5,4,3,2,1]}
[5,4,3,2,1]
示例 2：
输入：
head
=
[1,2]
\texttt{head = [1,2]}
head = [1,2]
输出：
[2,1]
\texttt{[2,1]}
[2,1]
示例 3：
输入：
head
=
[]
\texttt{head = []}
head = []
输出：
[]
\texttt{[]}
[]
数据范围
- 链表中结点的数目范围是 [0, 5000] \texttt{[0, 5000]} [0, 5000]
- -5000 ≤ Node.val ≤ 5000 \texttt{-5000} \le \texttt{Node.val} \le \texttt{5000} -5000≤Node.val≤5000
进阶
链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解法一
思路和算法
原始链表中，每个结点的 next \textit{next} next 指针都指向后一个结点。反转链表之后，每个结点的 next \textit{next} next 指针都指向前一个结点。因此，反转链表需要改变每个结点的 next \textit{next} next 指针指向的结点。
由于单链表中的每个结点都只有指向后一个结点的 next \textit{next} next 指针，因此需要另外存储前一个结点，在遍历链表的过程中完成反转。
具体做法是，维护两个变量 prev \textit{prev} prev 和 curr \textit{curr} curr 分别表示前一个结点和当前结点，初始时 prev = null \textit{prev} = \text{null} prev=null， curr = head \textit{curr} = \textit{head} curr=head。改变 curr \textit{curr} curr 的 next \textit{next} next 指针指向时，需要先得到其后面一个结点 next \textit{next} next，然后令 curr . next \textit{curr}.\textit{next} curr.next 指向 prev \textit{prev} prev，再将 prev \textit{prev} prev 和 curr \textit{curr} curr 都向后移动一步。对于链表中的每个结点进行上述操作，当 curr \textit{curr} curr 变成 null \text{null} null 时，遍历结束，此时完成链表的反转， prev \textit{prev} prev 指向反转后的链表的头结点。
下图为反转链表的例子。对于每个结点，需要将指向后一个结点的 next \textit{next} next 指针变成指向前一个结点。虚线表示 next \textit{next} next 指针原来的指向。
代码
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。需要遍历链表中的每个结点一次，每个结点的反转操作的时间都是 O ( 1 ) O(1) O(1)。
-
空间复杂度： O ( 1 ) O(1) O(1)。
解法二
思路和算法
也可以使用递归的方法反转列表。迭代的方法较简单，递归的方法相对复杂。
对于递归问题，首先需要考虑终止条件。这道题的终止条件是链表为空或者只有 1 1 1 个结点，此时不需要反转，直接返回链表即可。
当链表至少有 2 2 2 个结点时，首先将除了头结点以外的部分反转，然后改变头结点和头结点后面一个结点的 next \textit{next} next 指针的指向。
例如，原始链表为：
1 → 2 → 3 1 \rightarrow 2 \rightarrow 3 1→2→3
到达结点 3 3 3 时为递归的终止条件，回到结点 2 2 2。
到达结点 2 2 2 时， 3 3 3 已经反转完毕，将 3 3 3 的 next \textit{next} next 指针变成指向 2 2 2，将 2 2 2 的 next \textit{next} next 指针变成指向 null \text{null} null。此时链表为：
1 → 2 ← 3 1 \rightarrow 2 \leftarrow 3 1→2←3
到达结点 1 1 1 时， 2 2 2 和 3 3 3 已经反转完毕，将 2 2 2 的 next \textit{next} next 指针变成指向 1 1 1，将 1 1 1 的 next \textit{next} next 指针变成指向 null \text{null} null。此时链表为：
1 ← 2 ← 3 1 \leftarrow 2 \leftarrow 3 1←2←3
反转链表结束。
需要注意的是，递归过程中将当前结点的 next \textit{next} next 指针变成指向 null \text{null} null 是不可缺少的操作，否则链表中会出现环。
代码
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode second = head.next;
ListNode newHead = reverseList(second);
second.next = head;
head.next = null;
return newHead;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。需要对链表的每个结点进行反转操作，每个结点的反转操作的时间都是 O ( 1 ) O(1) O(1)。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。空间复杂度主要取决于递归调用栈的深度，递归调用栈最多不会超过 n n n 层。
解法三
思路和算法
解法二使用递归，空间复杂度是 O ( n ) O(n) O(n)。如果使用尾递归，则可以将空间复杂度优化至 O ( 1 ) O(1) O(1)。
尾递归的含义是，一个方法或函数中所有递归形式的调用都出现在方法或函数的末尾，则这个递归方法或函数是尾递归的。当递归调用是整个方法或函数体中最后执行的语句，且返回值不属于表达式的一部分时，递归调用就是尾递归。尾递归的特点是在回归过程中不用做任何操作，当编译器检测到尾递归时，会覆盖当前的栈帧而不是新建一个栈帧，从而优化栈空间。
这道题可以使用尾递归实现。使用尾递归实现，需要创建一个辅助方法，该辅助方法包含两个参数，分别是前一个结点 prev \textit{prev} prev 和当前结点 curr \textit{curr} curr。尾递归的具体实现如下：
-
终止条件是 curr = null \textit{curr} = \text{null} curr=null，此时返回 prev \textit{prev} prev；
-
当 curr ≠ null \textit{curr} \ne \text{null} curr=null 时，用 next \textit{next} next 表示 curr \textit{curr} curr 的后一个结点，令 curr . next \textit{curr}.\textit{next} curr.next 指向 prev \textit{prev} prev，然后用 curr \textit{curr} curr 和 next \textit{next} next 作为参数调用尾递归，返回值即为尾递归调用的返回值。
在主方法中调用尾递归方法时，参数为 prev = null \textit{prev} = \text{null} prev=null， curr = head \textit{curr} = \textit{head} curr=head，反转后的链表的头结点即为调用尾递归方法的返回值。
代码
class Solution {
public ListNode reverseList(ListNode head) {
return reverseListTail(null, head);
}
public ListNode reverseListTail(ListNode prev, ListNode curr) {
if (curr == null) {
return prev;
}
ListNode next = curr.next;
curr.next = prev;
return reverseListTail(curr, next);
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。需要对链表的每个结点进行反转操作，每个结点的反转操作的时间都是 O ( 1 ) O(1) O(1)。
-
空间复杂度： O ( 1 ) O(1) O(1)。