跳至主要內容

206. 反转链表


206. 反转链表open in new window

🟢   🔖  递归 链表  🔗 力扣open in new window LeetCodeopen in new window

题目

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),变量 prevcur 使用常数大小额外空间。

思路二:递归

使用递归法遍历链表,当越过尾节点后终止递归,在回溯时修改各节点的 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;
};

相关题目

题号标题题解标签难度
92反转链表 IIopen in new window[✓]链表
156上下翻转二叉树 🔒open in new window[✓] 深度优先搜索 二叉树
234回文链表open in new window[✓] 递归 链表 1+
2074反转偶数长度组的节点open in new window链表
2130链表最大孪生和open in new window 链表 双指针
2487从链表中移除节点open in new window 递归 链表 1+
2807在链表中插入最大公约数open in new window链表 数学 数论