Rust每日一题(14)--实现数据结构--删除链表的倒数第 N 个结点
- Po
- 更新于 2023-01-16 08:56
- 阅读 1626
Rust每日一题(14)--实现数据结构--删除链表的倒数第 N 个结点
leetcode地址 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1:
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1
输出：[]示例 3：
输入：head = [1,2], n = 1
输出：[1]难度: 中等
知识点
- 双指针扫描
- 所有权规则(否则编译很难通过)
- Option相关API
思路
- 首先扫描一遍整个链表的长度，然后对删除第n个节点；为了避免第一个节点被删除时需要特别处理，增加一个dummy节点指向head节点。
// Definition for singly-linked list. #[derive(PartialEq, Eq, Clone, Debug)] pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>> }
impl ListNode {
[inline]
fn new(val: i32) -> Self { ListNode { next: None, val } } }
struct Solution{
}
impl Solution { pub fn remove_nth_fromend(head:Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> { let mut dummy = Some(Box::new(ListNode{val:0,next: head.clone()})); let mut curr = &mut dummy; let mut count = 0; while let Some(node) = curr { curr = &mut node.next; count += 1; } println!("{}", count); curr = &mut dummy; for in 0..(count-n-1){ curr = &mut curr.as_mut().unwrap().next; } curr.as_mut().unwrap().next = curr.as_mut().unwrap().next.as_mut().unwrap().next.take(); return dummy.unwrap().next; } }
fn main(){ let list = vec![1,2,3,4,5]; let mut head = Some(Box::new(ListNode::new(list[0]))); let mut curr = head.as_mut(); for i in 1..list.len() { if let Some(mut node) = curr.take() { node.next = Some(Box::new(ListNode::new(list[i]))); curr = node.next.as_mut(); } } println!("{:?}", Solution::remove_nth_from_end(head,5)); }
2. 可以采用两个指针，第一个指针`curr`比第二个指针`next_curr`提前n个节点遍历，这样第一个指针遍历结束后，正好第二个指针遍历的位置就是待删除节点的前一个节点位置。impl Solution { pub fn remove_nth_from_end(mut head:Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> { let mut dummy = Some(Box::new(ListNode{val:0,next: head.clone()})); let mut curr = &mut head; let mut nextcurr = &mut dummy; // let mut count = 0; for in 0..n{ curr = &mut curr.as_mut().unwrap().next; };
while let Some(node) = curr.as_mut() {
curr = &mut node.next;
next_curr = &mut next_curr.as_mut().unwrap().next;
}
next_curr.as_mut().unwrap().next = next_curr.as_mut().unwrap().next.as_mut().unwrap().next.take();
return dummy.unwrap().next;
}}
