[閒聊] 每日leetcode 75 - Day14

[yam276 (史萊哲林的優等生)]

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
    }
}

但這效率就很差

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750233134.A.BFD.html
※ 編輯: yam276 (114.32.48.170 臺灣), 06/18/2025 15:52:36