[Leetcode 206] 反转链表

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定单链表的头节点head,反转链表,并返回反转后的链表。
示例 1:
notion image
示例 2:
notion image
示例 3:

解法一:双指针 (推荐)

next指针逐个“掉头”。
用两个指针维护已反转区待处理区的边界:
  • prev 指向已反转链表的表头(初始为 None
  • cur 指向当前要掉头的节点
每次把 cur.next 改指向 prev,然后整体向前推进。
复杂度
  • 时间:O(n)(每个节点只改一次指针)
  • 空间:O(1)(常数指针)

解法二:递归

先让后半段反转,再接上当前节点。
把“反转前半段 + 挂到后半段尾部”,交给递归的返回阶段完成。
复杂度
  • 时间:O(n)
  • 空间:O(n)(递归栈深度,最坏链型)
Buy Me a Coffee
上一篇
[Leetcode 204] 质数计数
下一篇
[Leetcode 208] 实现 Trie