We’re given a linked list of size n, where n will always be an even number. We’re asked to find the maximum twin sum. Twins are defined as two nodes, one from the beginning and one from the end. For example, in a linked list with size 4, twins would be (0, 3) and (1, 2).
To solve this, we first find the middle of the linked list using a slow and fast pointer. Then, from the slow pointer, we begin to reverse the second half of the linked list. After the second half of the linked list is reverse, we traverse both lists and find the maximum twin sum.
The solution is as follows:
class Solution:
def pairSum(self, head: Optional[ListNode]) -> int:
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
prev = None
curr = slow
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
ans = 0
while prev:
ans = max(ans, prev.val + head.val)
prev = prev.next
head = head.next
return ans_ Time Complexity:
O(n) - We traverse all nodes within the linked list.
_ Space Complexity:
O(1) - We maintain pointers that occupy constant space.