[闲聊] 每日leetcode 75 - Day12

楼主: yam276 ('_')   2025-06-16 14:53:23
328. Odd Even Linked List
题目:
对 Linked List 上所有节点重排序
改成奇数节点->偶数节点的顺序
思路:
Rust 的 Linked List 比较复杂
尤其这一题需要 in-place
不想使用 unsafe 的话就必须
1. 让 odd 借用 head
2. 建一个 even_head 剪掉 odd->next
3. 让 even 借用 even_head
遍历循环内也做类似的事情
1. 把 odd 接上
2. 把 odd 变成 odd->next
3. 剪掉更新后的 odd 的 odd->next 并接到 even->next
4. 判断 even-> next 是否为 none 是就跳出
5. 回到循环开头 odd 会自己判断 是否为 none 不继续
主要这语言要注意的
1. 你操作 node 要依靠 &mut Option<Box<T>> 有 &mut 才能操作自身
2. .as_mut() .take() .unwrap() 都是对 Option<T> 做的 (包装指标的操作)
4. Some(next_node) .next .val 这种东西都是对 Box<ListNode> 做的 (指标上的资料)
因为 ListNode 是资料
但需要 Box<T> 来包装才能有一个实际长度 (指标长度)
Box<T> 是指标本身
但这个场景 Box<T> 需要 Option<T> 包装才能实际使用
Box<T> 本身不能表达“没有东西”的状态
所以需要用 Option<Box<T>> 来表示“有可能没下一个节点”
像以下这样写就不合法
struct Node {
next: Box<Node> // illegal recursion
}
Code:
impl Solution {
pub fn odd_even_list(mut head: Option<Box<ListNode>>) -> Option<Box<
ListNode>> {
if head.is_none() || head.as_ref()?.next.is_none() {
return head;
}
let mut odd = head.as_mut().unwrap();
let mut even_head = odd.next.take();
let mut even = even_head.as_mut().unwrap();
while let Some(next_node) = even.next.take() {
odd.next = Some(next_node);
odd = odd.next.as_mut().unwrap();
even.next = odd.next.take();
if let Some(next_even) = even.next.as_mut() {
even = next_even;
} else {
break;
}
}
odd.next = even_head;
head
}
}
作者: sixB (6B)   2025-06-16 14:56:00
好厉害

Links booklink

Contact Us: admin [ a t ] ucptt.com