206. 反转链表
题目描述
给你单链表的头节点 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
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
方法一:双指针
只需要改变链表的next指针的指向,直接将链表反转即可,时间复杂度 O(n),空间复杂度 O(n)。其中 n 为链表的长度。
图示如下:
java
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head = prev;
return head;
}
}
ts
class Solution {
reverseList(head: ListNode | null): ListNode | null {
if (head === null) {
return head;
}
let prev: ListNode | null = null;
let curr: ListNode | null = head;
while (curr !== null) {
const next: ListNode | null = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
方法二:头插法
创建虚拟头节点
时间复杂度
图示如下:
java
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode();
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = next;
}
return dummy.next;
}
}
cpp
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = dummy->next;
dummy->next = curr;
curr = next;
}
return dummy->next;
}
};
ts
function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
let pre = null;
let cur = head;
while (cur != null) {
const next = cur.next;
cur.next = pre;
[pre, cur] = [cur, next];
}
return pre;
}
方法三:递归
递归反转链表的第二个节点到尾部的所有节点,然后
时间复杂度
java
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 递归调用,翻转第二个节点开始往后的链表
ListNode ans = reverseList(head.next);
// 翻转头节点与第二个节点的指向
head.next.next = head;
//此时的 head 节点为尾节点,next 需要指向 NULL
head.next = null;
return ans;
}
}
cpp
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* ans = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return ans;
}
};
ts
const rev = (pre: ListNode | null, cur: ListNode | null): ListNode | null => {
if (cur == null) {
return pre;
}
const next = cur.next;
cur.next = pre;
return rev(cur, next);
};
function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
const next = head.next;
head.next = null;
return rev(head, next);
}
python
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
ans = self.reverseList(head.next)
head.next.next = head
head.next = None
return ans
方法四:使用栈
时间复杂度
java
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
Stack<ListNode> stack = new Stack<>();
ListNode current = head;
while (current != null) {
stack.push(current);
current = current.next;
}
ListNode newHead = stack.pop();
current = newHead;
while (!stack.isEmpty()) {
ListNode node = stack.pop();
current.next = node;
current = node;
}
current.next = null;
return newHead;
}
}
ts
class Solution {
reverseList(head: ListNode | null): ListNode | null {
if (head === null || head.next === null) {
return head;
}
const stack: ListNode[] = [];
let current: ListNode | null = head;
while (current !== null) {
stack.push(current);
current = current.next;
}
const newHead: ListNode = stack.pop()!;
current = newHead;
while (stack.length > 0) {
const node = stack.pop()!;
current.next = node;
current = node;
}
current.next = null;
return newHead;
}
}