Leetcode 2130: Maximum Twin Sum of a Linked List

In this problem, we are working with Linked Lists and need to return the maximum sum of “twin” elements, defined in the following way:

In a linked list of size n, where n is even, the ith 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.
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.
The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

We are also given some examples and constraints:

Examples and constraints

The first implicit element that we need is the size of the list. We can compute it easily by simply traversing the list:

public int size(ListNode head) {
  if (head == null) {
    return 0;
  }
  return 1 + size(head.next);
}

This is a recursive implementation which could be also done with a simple while loop.

Then, I set the rule that I can’t use arrays to solve the problem. I believe that if an interviewer gives a ListNode structure, it is implied that we can’t solve the problem by changing the data structure to an array. One possible reason could be that the list node could be too…