2130. Maximum Twin Sum of a Linked List

Leetcode link

题目简介

/**
 * @param {ListNode} head
 * @return {number}
 */

题目给我们一个链表 head，链表元素长度为 len，len 为偶数

要求我们给 [0, len-1], [1, len-2], ... 的值求和，并返回最大的和

解题思路

这题需要分为两步来求解：反转链表、求和比大小

在反转链表部分，我们不需要反转整个链表，我们只需要反转前半部分的链表即可

当前半部分链表被反转之后，我们只需要同步遍历两个链表求和最后保存最大值返回即可

Javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number}
 */
var pairSum = function (head) {
    // revrese the first half of the list
    let prev = null
    let slow = head
    let next = slow.next
    let fast = head

    while (fast && fast.next) {
        fast = fast.next.next
        slow.next = prev
        prev = slow
        slow = next
        next = next.next
    }

    // now we have 2 list: prev and slow
    let res = -1
    while(prev) {
        const val = prev.val + slow.val
        res = Math.max(val, res)
        prev = prev.next
        slow = slow.next
    }
    return res


};