SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a singly linked list, the goal is to find the maximum twin sum of the list. A twin sum is defined as the sum of a node's value and its counterpart from the other end of the list. Specifically, we pair the first node with the last node, the second node with the second last node, and so on. We want to find the maximum of these sums.

Intuition

The problem requires us to find pairs of nodes in a linked list that are equidistant from the ends and compute their sums. The maximum of these sums is our desired result. This problem can be effectively solved by splitting the list into two halves, reversing the second half, and then comparing corresponding elements in the two halves.

Approach

1. Find the middle of the list: We use the two-pointer technique, where one pointer moves twice as fast as the other. By the time the fast pointer reaches the end, the slow pointer will be at the midpoint.

2. Reverse the second half of the list: Starting from the middle node, we reverse the second half of the linked list. This allows us to easily compare the nodes in the first half with their corresponding nodes in the reversed second half.

3. Compute the twin sums: With the first half and the reversed second half, iterate through the nodes and calculate the sum of each pair of nodes. Track the maximum sum encountered.

4. Return the maximum twin sum as the result.

Complexity

Time Complexity:

O(n) - The list is traversed multiple times, but each operation (finding the middle, reversing the second half, and calculating the sums) takes linear time.

Space Complexity:

O(1) - No extra space is required other than a few pointers, making the space complexity constant.

Code

C++

class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *slow = head, *fast = head;

        // Move `slow` to the middle of the list
        while (fast && fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Reverse the second half of the list
        fast = slow->next;
        slow->next = nullptr;
        ListNode* prev = nullptr;
        while (fast) {
            ListNode* nextNode = fast->next;
            fast->next = prev;
            prev = fast;
            fast = nextNode;
        }

        // Calculate the maximum pair sum
        int maxSum = 0;
        ListNode* pr = prev;
        while (pr) {
            maxSum = max(maxSum, pr->val + head->val);
            pr = pr->next;
            head = head->next;
        }

        return maxSum;
    }
};

Python

class Solution:
    def pairSum(self, head: ListNode) -> int:
        slow, fast = head, head

        # Move `slow` to the middle of the list
        while fast and fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half of the list
        fast = slow.next
        slow.next = None
        prev = None
        while fast:
            next_node = fast.next
            fast.next = prev
            prev = fast
            fast = next_node

        # Calculate the maximum pair sum
        max_sum = 0
        pr = prev
        while pr:
            max_sum = max(max_sum, pr.val + head.val)
            pr = pr.next
            head = head.next

        return max_sum

Java

class Solution {
    public int pairSum(ListNode head) {
        ListNode slow = head, fast = head;

        // Move `slow` to the middle of the list
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse the second half of the list
        fast = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (fast != null) {
            ListNode nextNode = fast.next;
            fast.next = prev;
            prev = fast;
            fast = nextNode;
        }

        // Calculate the maximum pair sum
        int maxSum = 0;
        ListNode pr = prev;
        while (pr != null) {
            maxSum = Math.max(maxSum, pr.val + head.val);
            pr = pr.next;
            head = head.next;
        }

        return maxSum;
    }
}

JavaScript

var pairSum = function (head) {

    let slow = head;
    let fast = head;

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

    fast = slow.next;
    slow.next = null;
    let v = fast;
    let pr = null;
    while (v) {
        let d = v.next;
        v.next = pr;
        pr = v;
        v = d;
    }
    let max = 0;
    console.log(pr, head)
    while (pr) {
        max = Math.max(max, pr.val + head.val);
        pr = pr.next;
        head = head.next;
    }
    return max;
};