2130. Maximum Twin Sum of a Linked List
题目：
求 Linked List 每一对 nums[index] + nums[nums.len() - index - 1]
的最大值
思路：
正常作法是要用反转 Linked List
也就是先走一轮确定个数 n
再根据 n / 2 反转前半的 node
这样一起跑就一定成对 相加后每次比较
Code:
impl Solution {
pub fn pair_sum(head: Option<Box<ListNode>>) -> i32 {
let mut current = head.as_ref();
let mut count = 0;
while current.is_some() {
count += 1;
current = current.unwrap().next.as_ref();
}
let mut head = head;
let mut prev = None;
let mut next = None;
for _ in 0..count / 2 {
if let Some(mut node) = head {
next = node.next.take();
node.next = prev;
prev = Some(node);
head = next;
}
}
let mut max_sum = 0;
while let (Some(node1), Some(node2)) = (prev, head) {
max_sum = max_sum.max(node1.val + node2.val);
prev = node1.next;
head = node2.next;
}
max_sum
}
}
或是你可以比较懒 存进 Vec
impl Solution {
pub fn pair_sum(head: Option<Box<ListNode>>) -> i32 {
let mut max_sum = 0;
let mut nums = Vec::new();
let mut curr = head.as_ref();
while let Some(n) = curr {
nums.push(n.val);
curr = n.next.as_ref();
}
let n = nums.len();
for index in 0..(n / 2) {
max_sum = max_sum.max(nums[index] + nums[n - index - 1]);
}
max_sum
}
}
但这效率就很差