I’m using Java to solve this LeetCode question:
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.
I’m currently using an ArrayList to store the members of the linked list and then calculating the sum. However, my solution is resulting in a “memory limit exceeded” question failure. How can I fix this?
Here’s my solution so far:
class Solution {
public int pairSum(ListNode head) {
ArrayList<Integer> temp = new ArrayList<>();
ListNode current = head;
while(current != null){
temp.add(current.val);
}
int n = temp.size();
int sum = 0;
int maxSum = 0;
if(temp.size() == 2){
return temp.get(0) + temp.get(1);
}
for(int i = 0; i < n/2; i++){
sum = sum + temp.get(i) + temp.get(n - i - 1);
maxSum = Math.max(sum, maxSum);
}
return maxSum;
}
}
1
You have an infinite loop at the start as you never advance current
past the head. You can rewrite it like so:
for (ListNode current = head; current != null; current = current.next)
temp.add(current.val);
Furthermore, your solution is incorrect as you should not be accumulating a sum of all twin nodes. The answer should be updated like this:
maxSum = Math.max(sum, temp.get(i) + temp.get(n - i - 1));
1