2130. Maximum Twin Sum of a Linked List Medium

1/**
2 * [2130] Maximum Twin Sum of a Linked List
3 *
4 * In a linked list of size n, where n is even, the i^th node (0-indexed) of the linked list is known as the twin of the (n-1-i)^th node, if 0 <= i <= (n / 2) - 1.
5 * 
6 * 	For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
7 * 
8 * The twin sum is defined as the sum of a node and its twin.
9 * Given the head of a linked list with even length, return the maximum twin sum of the linked list.
10 *  
11 * Example 1:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/03/eg1drawio.png" style="width: 250px; height: 70px;" />
13 * Input: head = [5,4,2,1]
14 * Output: 6
15 * Explanation:
16 * Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
17 * There are no other nodes with twins in the linked list.
18 * Thus, the maximum twin sum of the linked list is 6. 
19 * 
20 * Example 2:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/03/eg2drawio.png" style="width: 250px; height: 70px;" />
22 * Input: head = [4,2,2,3]
23 * Output: 7
24 * Explanation:
25 * The nodes with twins present in this linked list are:
26 * - Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
27 * - Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
28 * Thus, the maximum twin sum of the linked list is max(7, 4) = 7. 
29 * 
30 * Example 3:
31 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/03/eg3drawio.png" style="width: 200px; height: 88px;" />
32 * Input: head = [1,100000]
33 * Output: 100001
34 * Explanation:
35 * There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	The number of nodes in the list is an even integer in the range [2, 10^5].
41 * 	1 <= Node.val <= 10^5
42 * 
43 */
44pub struct Solution {}
45use crate::util::linked_list::{ListNode, to_list};
46
47// problem: https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/
48// discuss: https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52// Definition for singly-linked list.
53// #[derive(PartialEq, Eq, Clone, Debug)]
54// pub struct ListNode {
55//   pub val: i32,
56//   pub next: Option<Box<ListNode>>
57// }
58// 
59// impl ListNode {
60//   #[inline]
61//   fn new(val: i32) -> Self {
62//     ListNode {
63//       next: None,
64//       val
65//     }
66//   }
67// }
68impl Solution {
69    pub fn pair_sum(head: Option<Box<ListNode>>) -> i32 {
70        0
71    }
72}
73
74// submission codes end
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn test_2130() {
82    }
83}
84