Maximum Twin Sum of a Linked List

Med

#1940Time: O(n), where n is the number of nodes. The first traversal to populate the list takes O(n) time, and the second pass with two pointers takes O(n/2) = O(n) time.Space: O(n), as we need an `ArrayList` to store the values of all n nodes in the linked list.1 company

Patterns

Two Pointers

Data structures

Linked List Stack

Companies

josh technology

Prompt

In a linked list of size n, where n is even, the i^th 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.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

The number of nodes in the list is an even integer in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to first convert the linked list into a more flexible data structure like an ArrayList. By storing all node values in an array, we can easily access any element by its index. This allows us to pair the i-th element with the (n-1-i)-th element directly.

Algorithm

Create an empty java.util.ArrayList<Integer> to store the node values.
Traverse the linked list from the head, adding each node's value to the ArrayList.
Initialize a variable maxTwinSum to 0.
Initialize two pointers, left = 0 and right = list.size() - 1.
Loop while left < right:
- a. Calculate currentSum = list.get(left) + list.get(right).
- b. Update maxTwinSum = Math.max(maxTwinSum, currentSum).
- c. Increment left and decrement right.
Return maxTwinSum.

Walkthrough

First, we iterate through the entire linked list from head to tail. During this traversal, we add the value of each node to an ArrayList. After the list is fully traversed, the ArrayList contains all the node values in order.

We then use a two-pointer technique on the ArrayList. One pointer (left) starts at the beginning (index 0), and the other (right) starts at the end (index n-1). We iterate as long as left is less than right. In each iteration, we calculate the sum of the values at the left and right indices, which corresponds to a twin sum. We keep track of the maximum sum found so far. After each sum calculation, we move the pointers closer to the center (left++, right--). The loop terminates when the pointers meet or cross, at which point we have checked all twin pairs. The maximum sum recorded is the result.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public int pairSum(ListNode head) {13        java.util.List<Integer> values = new java.util.ArrayList<>();14        ListNode current = head;15        while (current != null) {16            values.add(current.val);17            current = current.next;18        }19 20        int left = 0;21        int right = values.size() - 1;22        int maxTwinSum = 0;23 24        while (left < right) {25            int currentSum = values.get(left) + values.get(right);26            maxTwinSum = Math.max(maxTwinSum, currentSum);27            left++;28            right--;29        }30 31        return maxTwinSum;32    }33}

Complexity

Time

O(n), where n is the number of nodes. The first traversal to populate the list takes O(n) time, and the second pass with two pointers takes O(n/2) = O(n) time.

Space

O(n), as we need an `ArrayList` to store the values of all n nodes in the linked list.

Trade-offs

Pros

Simple to understand and implement.
Does not modify the original linked list structure.

Cons

Requires extra space proportional to the size of the linked list, which can be significant for large lists.

A more space-efficient approach involves reversing the second half of the linked list in-place. This allows us to traverse the first half and the (reversed) second half simultaneously to find the twin sums without using extra storage.

Algorithm

Use two pointers, slow and fast, both starting at head.
Move slow one step and fast two steps at a time until fast reaches the end of the list. slow will now be at the middle.
Reverse the linked list starting from slow. Let the head of this new reversed list be secondHalfHead.
Initialize maxTwinSum to 0.
Initialize a pointer firstHalfHead to the original head.
Iterate while secondHalfHead is not null:
- a. Calculate currentSum = firstHalfHead.val + secondHalfHead.val.
- b. Update maxTwinSum = Math.max(maxTwinSum, currentSum).
- c. Move both pointers forward: firstHalfHead = firstHalfHead.next and secondHalfHead = secondHalfHead.next.
Return maxTwinSum.

Walkthrough

This method consists of three main steps:

Find the middle: We use the classic "slow and fast pointer" technique. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end of the list, the slow pointer will be at the beginning of the second half.
Reverse the second half: Starting from the node indicated by the slow pointer, we reverse the remainder of the list. This creates a new, reversed sub-list representing the second half.
Calculate twin sums: We now have two pointers: one at the original head of the list (p1) and another at the head of the reversed second half (p2). We iterate through both halves, summing p1.val and p2.val at each step. We keep track of the maximum sum encountered. Since both halves have n/2 nodes, the loop runs n/2 times.

This approach cleverly manipulates the list's pointers to achieve the goal with constant extra space.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public int pairSum(ListNode head) {13        // 1. Find the middle of the linked list14        ListNode slow = head;15        ListNode fast = head;16        while (fast != null && fast.next != null) {17            slow = slow.next;18            fast = fast.next.next;19        }20 21        // 2. Reverse the second half of the list22        ListNode secondHalfHead = reverseList(slow);23 24        // 3. Calculate twin sums25        ListNode p1 = head;26        ListNode p2 = secondHalfHead;27        int maxTwinSum = 0;28        while (p2 != null) {29            int currentSum = p1.val + p2.val;30            maxTwinSum = Math.max(maxTwinSum, currentSum);31            p1 = p1.next;32            p2 = p2.next;33        }34 35        return maxTwinSum;36    }37 38    private ListNode reverseList(ListNode head) {39        ListNode prev = null;40        ListNode current = head;41        while (current != null) {42            ListNode nextNode = current.next;43            current.next = prev;44            prev = current;45            current = nextNode;46        }47        return prev;48    }49}

Complexity

Time

O(n). Finding the middle takes O(n), reversing the second half takes O(n), and calculating the sums takes O(n). The total time complexity is linear.

Space

O(1). This approach only uses a constant amount of extra space for pointers, regardless of the list's size.

Trade-offs

Pros

Highly space-efficient, using only constant extra space.
Optimal solution for this problem.

Cons

More complex to implement than the ArrayList approach.
Modifies the structure of the original linked list. (Though it could be restored with another reversal pass if needed).

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int pairSum ( ListNode head ) { List < Integer > s = new ArrayList <>(); for (; head != null ; head = head . next ) { s . add ( head . val ); } int ans = 0 , n = s . size (); for ( int i = 0 ; i < ( n >> 1 ); ++ i ) { ans = Math . max ( ans , s . get ( i ) + s . get ( n - 1 - i )); } return ans ; } }

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int pairSum ( ListNode * head ) { vector < int > s ; for (; head != nullptr ; head = head -> next ) s . push_back ( head -> val ); int ans = 0 , n = s . size (); for ( int i = 0 ; i < ( n >> 1 ); ++ i ) ans = max ( ans , s [ i ] + s [ n - i - 1 ]); return ans ; } };

1# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def pairSum ( self , head : Optional [ ListNode ]) -> int : s = [] while head : s . append ( head . val ) head = head . next n = len ( s ) return max ( s [ i ] + s [ - ( i + 1 )] for i in range ( n >> 1 ))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem