050.md

2130. Maximum Twin Sum of a Linked List

Difficulty: 🟡 Medium

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.

Examples:

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, 105].
• 1 <= Node.val <= 105

Solutions

O(n) solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def _get_middle(self, head: Optional[ListNode]):
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def _reverse_nodes_untill_middle(self, head: Optional[ListNode], middle: Optional[ListNode]) -> Optional[ListNode]:
        new_head = None
        while head != middle:
            node = head
            head = head.next
            node.next = new_head
            new_head = node
        return new_head

    def pairSum(self, head: Optional[ListNode]) -> int:
        middle = self._get_middle(head)
        reversed_head = self._reverse_nodes_untill_middle(head, middle)
        maximum = 0
        while middle and reversed_head:
            maximum = max(maximum, middle.val+reversed_head.val)
            middle = middle.next 
            reversed_head = reversed_head.next
        return maximum

The given solution approach follows these steps:

1. Find the middle node of the linked list using the slow and fast pointer technique.
2. Reverse the nodes of the linked list until the middle node. This can be done by iterating over the nodes from the head, updating the next pointer of each node to the previous node.
3. Iterate over the remaining nodes from the middle node and the reversed head, calculating the sum of each pair and keeping track of the maximum sum.
4. Return the maximum twin sum.

The solution uses three helper functions:

1. _get_middle: Finds the middle node of the linked list using the slow and fast pointer technique. It returns the middle node.
2. _reverse_nodes_untill_middle: Reverses the nodes of the linked list until the middle node. It takes the head node and the middle node as parameters and returns the new head after the reversal.
3. pairSum: Implements the main logic to find the maximum twin sum. It takes the head node as a parameter and returns the maximum twin sum.

Complexity Analysis

The time complexity of the algorithm is O(n), where n is the number of nodes in the linked list. The algorithm iterates over the linked list once to find the middle node and reverses the nodes until the middle node.

The space complexity of the algorithm is O(1) because it uses a constant amount of additional space.

Summary

The given solution finds the maximum twin sum in a linked list of even length. It uses the slow and fast pointer technique to find the middle node and then reverses the nodes until the middle node. It iterates over the remaining nodes and calculates the sum of each pair, keeping track of the maximum sum. The algorithm has a time complexity of O(n) and a space complexity of O(1).

NB: If you want to get community points please suggest solutions in other languages as merge requests.