LeetCode每日一题(2095. Delete the Middle Node of a Linked List)

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]

Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.

Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]

Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]
Output: [2]

Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 1 <= Node.val <= 105

---

用快慢指针法， 快指针一次走两步， 慢指针一次走一步, 最后快指针到头的时候慢指针所指的就是 list 的中点， 但是要注意的是我们要做操作的地方其实应该是中点节点的前一个节点，所以我们在决定慢指针是不是要往前走的时候，不光要考虑快指针是不是已经成功走了 2 步， 还要考虑快指针指向的节点有没有下一个节点。如果没有则也需要跳出循环，以让慢指针保持在中点节点之前。还有需要注意的地方就是只有 1 个节点的情况， 如果快慢指针都指向同一个位置，那证明 list 只有 1 个节点。

最后说一句， 用 rust 写快慢指针真的不容易

---

impl Solution {
    pub fn delete_middle(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        unsafe {
            let mut slow = &mut head as *mut Option<Box<ListNode>>;
            let mut fast = &mut head as *mut Option<Box<ListNode>>;
            while let Some(f) = (*fast).as_mut() {
                if let Some(ff) = &mut f.next {
                    if let Some(fff) = &mut ff.next {
                        if fff.next.is_some() {
                            fast = (&mut ff.next) as *mut Option<Box<ListNode>>;
                            slow =
                                (&mut (*slow).as_mut().unwrap().next) as *mut Option<Box<ListNode>>;
                            continue;
                        }
                        fast = (&mut f.next) as *mut Option<Box<ListNode>>;
                        break;
                    }
                    fast = (&mut f.next) as *mut Option<Box<ListNode>>;
                    break;
                }
                break;
            }
            if slow == fast {
                return None;
            }
            let slow_next = (*slow).as_mut().unwrap().next.take();
            if slow_next.is_some() {
                let slow_next_next = slow_next.unwrap().next.take();
                (*slow).as_mut().unwrap().next = slow_next_next;
            }
        }
        head
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35