Description

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.

Example 1:

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

Example 2:

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

Example 3:

1Input: head = [1,100000]
2Output: 100001
3Explanation:
4There 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, 105].
  • 1 <= Node.val <= 10^5

Solution

Using Array

This problem mentions that the number of nodes in the list is even. So, we will always have twin for each number. The easiest solution would be to convert this linked list into something that will have indices associated with it (an array). Once we have those numbers stored in an array, we can simply use its indices to find twin for each number. This will require two iterations and will result in time complexity of O(n).

 1class Solution {
 2    public int pairSum(ListNode head) {
 3        ListNode current = head;
 4        List<Integer> numbers = new ArrayList<>();
 5        while (current != null) {
 6            numbers.add(current.val);
 7            current = current.next;
 8        }
 9
10        int maxTwinSum = 0;
11        int i = 0, j = numbers.size() - 1;
12        while (i < j) {
13            maxTwinSum = Math.max(maxTwinSum, numbers.get(i) + numbers.get(j));
14            i++;
15            j--;
16        }
17        return maxTwinSum;
18    }
19}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Using Fast and Slow Pointers

We can reverse the second half of the list to find the twin for a node. To find the second half, we have to first find the middle of the list. We can use fast and slow pointers to find the middle of the list. Once we have found the middle, we can reverse the second half of the list and create prev node. Once we have both head and prev, we can easily calculate twin sum using prev node and head node. The prev node is very similar to tail except that it will have null at the middle of the node. This way we do not need to go past half and list. Alternatively, we could store the middle of the list in a new node middle and every time we can check if we have reached middle node.

 1class Solution {
 2    public int pairSum2(ListNode head) {
 3        // Find the middle of the list
 4        ListNode slow = head, fast = head;
 5        while (fast != null && fast.next != null) {
 6            slow = slow.next;
 7            fast = fast.next.next;
 8        }
 9        ListNode middle = slow;
10
11        // Reverse the second half to find the tail (prev) node
12        ListNode prev = null, current = middle, next;
13        while (current != null) {
14            next = current.next;
15            current.next = prev;
16            prev = current;
17            current = next;
18        }
19
20        // Find the maximum twin sum
21        int maxTwinSum = 0;
22        while (head != middle) {
23            maxTwinSum = Math.max(maxTwinSum, head.val + prev.val);
24            head = head.next;
25            prev = prev.next;
26        }
27        return maxTwinSum;
28    }
29}
  • Time Complexity: O(n)
  • Space Complexity: O(1)