2074. Reverse Nodes in Even Length Groups Medium

1/**
2 * [2074] Reverse Nodes in Even Length Groups
3 *
4 * You are given the head of a linked list.
5 * The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,
6 * 
7 * 	The 1^st node is assigned to the first group.
8 * 	The 2^nd and the 3^rd nodes are assigned to the second group.
9 * 	The 4^th, 5^th, and 6^th nodes are assigned to the third group, and so on.
10 * 
11 * Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.
12 * Reverse the nodes in each group with an even length, and return the head of the modified linked list.
13 *  
14 * Example 1:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/25/eg1.png" style="width: 699px; height: 124px;" />
16 * Input: head = [5,2,6,3,9,1,7,3,8,4]
17 * Output: [5,6,2,3,9,1,4,8,3,7]
18 * Explanation:
19 * - The length of the first group is 1, which is odd, hence no reversal occurs.
20 * - The length of the second group is 2, which is even, hence the nodes are reversed.
21 * - The length of the third group is 3, which is odd, hence no reversal occurs.
22 * - The length of the last group is 4, which is even, hence the nodes are reversed.
23 * 
24 * Example 2:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/25/eg2.png" style="width: 284px; height: 114px;" />
26 * Input: head = [1,1,0,6]
27 * Output: [1,0,1,6]
28 * Explanation:
29 * - The length of the first group is 1. No reversal occurs.
30 * - The length of the second group is 2. The nodes are reversed.
31 * - The length of the last group is 1. No reversal occurs.
32 * 
33 * Example 3:
34 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/17/ex3.png" style="width: 348px; height: 114px;" />
35 * Input: head = [1,1,0,6,5]
36 * Output: [1,0,1,5,6]
37 * Explanation:
38 * - The length of the first group is 1. No reversal occurs.
39 * - The length of the second group is 2. The nodes are reversed.
40 * - The length of the last group is 2. The nodes are reversed.
41 * 
42 *  
43 * Constraints:
44 * 
45 * 	The number of nodes in the list is in the range [1, 10^5].
46 * 	0 <= Node.val <= 10^5
47 * 
48 */
49pub struct Solution {}
50use crate::util::linked_list::{ListNode, to_list};
51
52// problem: https://leetcode.com/problems/reverse-nodes-in-even-length-groups/
53// discuss: https://leetcode.com/problems/reverse-nodes-in-even-length-groups/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57// Definition for singly-linked list.
58// #[derive(PartialEq, Eq, Clone, Debug)]
59// pub struct ListNode {
60//   pub val: i32,
61//   pub next: Option<Box<ListNode>>
62// }
63// 
64// impl ListNode {
65//   #[inline]
66//   fn new(val: i32) -> Self {
67//     ListNode {
68//       next: None,
69//       val
70//     }
71//   }
72// }
73impl Solution {
74    pub fn reverse_even_length_groups(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
75        Some(Box::new(ListNode::new(0)))
76    }
77}
78
79// submission codes end
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_2074() {
87    }
88}
89