[閒聊] 每日leetcode 75 - Day12

[yam276 (史萊哲林的優等生)]

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
    }
}


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750056805.A.CB7.html
→ sixB: 好厲害
※ 編輯: yam276 (60.248.143.163 臺灣), 06/16/2025 15:04:51