206. Reverse Linked List

🟢   🔖  递归 链表  🔗 LeetCode

题目

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]

Output: [2,1]

Example 3:

Input: head = []

Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

题目大意

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路

有两种解题方法，一是循环、二是递归。

思路一：循环

使用双指针，遍历链表，并在访问各节点时修改 next 引用指向。

时间复杂度 O(n) ： 遍历链表使用线性大小时间。

空间复杂度 O(1) ： 变量 prev 和 cur 使用常数大小额外空间。

思路二：递归

使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。

时间复杂度 O(n) ： 遍历链表使用线性大小时间。

空间复杂度 O(n) ： 遍历链表的递归深度达到 n ，系统使用 O(n) 大小额外空间。

代码

循环

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
	let prev = null;
	let cur = head;

	while (cur !== null) {
		let next = cur.next;
		cur.next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
};

递归

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
	if (head === null || head.next === null) {
		return head;
	}
	const last = reverseList(head.next);
	head.next.next = head;
	head.next = null;
	return last;
};

相关题目

相关题目

• 92. 反转链表 II
• 🔒 Binary Tree Upside Down
• 234. 回文链表
• 2074. 反转偶数长度组的节点
• 2130. 链表最大孪生和
• 2487. 从链表中移除节点
• 2807. Insert Greatest Common Divisors in Linked List

- [92. 反转链表 II](./0092.md)
- [🔒 Binary Tree Upside Down](https://leetcode.com/problems/binary-tree-upside-down)
- [234. 回文链表](./0234.md)
- [2074. 反转偶数长度组的节点](https://leetcode.com/problems/reverse-nodes-in-even-length-groups)
- [2130. 链表最大孪生和](https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list)
- [2487. 从链表中移除节点](https://leetcode.com/problems/remove-nodes-from-linked-list)
- [2807. Insert Greatest Common Divisors in Linked List](https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list)