🧩 Week 1 · Day 4 — LeetCode Hot 100
1️⃣ 反转链表
🧠 题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
💡 思路解析：迭代反转法
使用 三个指针：
-
pre：指向反转后的前一个节点； -
cur：当前节点； -
nxt：暂存下一个节点，防止链表断开。
遍历链表，逐步让 cur.next 指向 pre，直到链表结束。
🧾 代码实现
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next # 暂存下一个节点
cur.next = pre # 反转指针
pre = cur # pre 前移
cur = nxt # cur 前移
return pre # 返回反转后的头节点
🔍 补充：递归写法
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_head
递归的核心思想：
反转子链表后，让 head.next 的 next 指向 head，最后断开 head.next。
2️⃣ 回文链表
🧠 题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
如果是，返回 True；否则，返回 False。
💡 思路解析：快慢指针 + 反转后半部分
-
快慢指针 找到链表中点；
-
反转后半链表；
-
前后指针对比 判断是否为回文；
-
（可选）再将链表恢复为原状态。
🧾 代码实现
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # 当 fast 到尾部时，slow 在中间
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, cur = None, head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return True
# 1️⃣ 找中点
mid = self.middleNode(head)
# 2️⃣ 反转后半链表
head2 = self.reverseList(mid)
# 3️⃣ 前后对比
cur1, cur2 = head, head2
while cur2:
if cur1.val != cur2.val:
return False
cur1 = cur1.next
cur2 = cur2.next
return True
⚙️ 时间与空间复杂度
-
时间复杂度：O(n)
-
空间复杂度：O(1)
3️⃣ 环形链表
🧠 题目描述
给定一个链表的头节点 head，判断链表中是否有环。
如果存在某个节点，通过连续跟踪 next 指针能再次到达该节点，则说明存在环。
💡 思路解析：快慢指针法（Floyd 判圈算法）
使用两个指针：
-
slow：每次走一步； -
fast：每次走两步。
若存在环，fast 一定会在环中追上 slow；
若无环，fast 会先到达链表尾（None）。
🧾 代码实现
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
⚙️ 时间与空间复杂度
-
时间复杂度：O(n)
-
空间复杂度：O(1)
🧩 进阶：如何找到环的入口？
在检测到环后：
-
让一个指针从头开始；
-
另一个指针从相遇点开始；
-
两个指针每次都走一步；
-
它们再次相遇的节点，就是 环的入口。