19. 删除链表的倒数第 N 个结点 Remove-nth-node-from-end-of-list
给你一个链表，删除链表的倒数第 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]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
代码：
pub struct ListNode { pub data: i32, pub next: Option<Box<ListNode>>, } impl ListNode { pub fn new(val: i32) -> Self { ListNode { next: None, data: val, } } pub fn build(&mut self, list: Vec<i32>) { // 倒序建立链表 for i in (0..list.len()).rev() { let node = ListNode { data: list[i], next: self.next.take(), }; self.next = Some(Box::new(node)); } } pub fn travel(&self) { let mut p = self.next.as_ref(); while let Some(node) = p { print!("{}{}", node.data, if node.next.is_some() { "->" } else { "" }); p = node.next.as_ref(); } println!("<nil>"); } } fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> { let mut head = head; let mut count = 0; // 遍历链表并计数 let mut p = head.as_ref(); while let Some(node) = p { count += 1; p = node.next.as_ref(); } // 计算要删除的节点的索引 let m = count - n; if m == 0 { // 如果删除的是头节点，则直接返回第二个节点 return head.unwrap().next; } // 遍历链表并删除节点，注意需要显式修改前一个节点的指针 let mut p = head.as_mut(); for _ in 1..m { p = p.unwrap().next.as_mut(); } let node_to_be_deleted = p.as_mut().unwrap().next.take().unwrap(); p.as_mut().unwrap().next = node_to_be_deleted.next; head } fn main() { let mut head = Box::new(ListNode { data: 0, next: None }); head.build(vec![1, 2, 3, 4, 5]); head.travel(); head = remove_nth_from_end(Some(head), 2).unwrap(); head.travel(); head = Box::new(ListNode { data: 0, next: None }); head.build(vec![1]); head.travel(); head = remove_nth_from_end(Some(head), 1).unwrap(); head.travel(); head = Box::new(ListNode { data: 0, next: None }); head.build(vec![1, 2]); head.travel(); head = remove_nth_from_end(Some(head), 1).unwrap(); head.travel(); }
输出：
1->2->3->4->5<nil>
1->2->3->5<nil>
1<nil>
<nil>
1->2<nil>
1<nil>
20. 有效的括号 Valid Parentheses
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 10^4
s 仅由括号 '()[]{}' 组成
代码：
fn is_valid(s: String) -> bool { let mut stack = Vec::<u8>::new(); for ch in s.chars() { match ch { '(' => stack.push(b'('), '[' => stack.push(b'['), '{' => stack.push(b'{'), ')' => { if let Some(c) = stack.pop() { if c != b'(' { return false; } } else { return false; } } ']' => { if let Some(c) = stack.pop() { if c != b'[' { return false; } } else { return false; } } '}' => { if let Some(c) = stack.pop() { if c != b'{' { return false; } } else { return false; } } _ => {} } } stack.is_empty() } fn main() { println!("{}", is_valid("()".to_string())); println!("{}", is_valid("()[]{}".to_string())); println!("{}", is_valid("(]".to_string())); println!("{}", is_valid("([)]".to_string())); println!("{}", is_valid("{()}".to_string())); }
输出：
true
true
false
false
true
21. 合并两个有序链表 Mmerge-two-sorted-lists
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
代码：
pub struct ListNode { pub data: i32, pub next: Option<Box<ListNode>>, } impl ListNode { pub fn new(val: i32) -> Self { ListNode { next: None, data: val, } } pub fn build(&mut self, list: Vec<i32>) { for i in (0..list.len()).rev() { let p = ListNode { data: list[i], next: self.next.take(), }; self.next = Some(Box::new(p)); } } pub fn travel(&self) { let mut p = self.next.as_ref(); while let Some(node) = p { print!("{}{}", node.data, if node.next.is_some() { "->" } else { "" }); p = node.next.as_ref(); } println!("<nil>"); } } fn merge_two_lists(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> { let mut res = Box::new(ListNode::new(-1)); let mut p = &mut res; while l1.is_some() && l2.is_some() { let val; if l1.as_ref().unwrap().data < l2.as_ref().unwrap().data { val = l1.as_ref().unwrap().data; l1 = l1.unwrap().next; } else { val = l2.as_ref().unwrap().data; l2 = l2.unwrap().next; } p.next = Some(Box::new(ListNode::new(val))); p = p.next.as_mut().unwrap(); } if l1.is_some() { p.next = l1; } else if l2.is_some() { p.next = l2; } res.next } fn main() { let mut l1 = Box::new(ListNode::new(0)); let mut l2 = Box::new(ListNode::new(0)); l1.build(vec![1, 2, 4]); l2.build(vec![1, 3, 4]); l1.travel(); l2.travel(); let result = merge_two_lists(l1.next, l2.next).unwrap(); result.travel(); }
输出：
1->2->4<nil>
1->3->4<nil>
1->2->3->4->4<nil>?有待改正
