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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| // @lc code=start
// 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
// }
// }
// }
impl Solution {
/// ## 解题思路
/// - 栈
pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
if k <= 1 || head.is_none() {
return head;
}
let mut dummy = ListNode::new(0);
let mut cur_ref = &mut dummy.next;
let mut stack = vec![]; //临时栈
let mut head = head;
while let Some(mut node) = head.take() { // 依次取下头节点
head = node.next.take();
stack.push(node);
// 如果临时栈中的元素个数达到k
if stack.len() == k as usize {
// 依次弹出栈中的元素
while stack.len() > 0 {
*cur_ref = stack.pop();
cur_ref = &mut cur_ref.as_mut().unwrap().next;
}
}
}
while stack.len() > 0 {
*cur_ref = Some(stack.remove(0));
cur_ref = &mut cur_ref.as_mut().unwrap().next;
}
*cur_ref = None;
dummy.next
}
}
// @lc code=end
|
