Sponsored
Sponsored
The idea is to reverse the second half of the linked list and utilize the twin's definition by simultaneously traversing the first half from the beginning and the reversed half from the end. As you do this traversal, calculate the twin sums and keep track of the maximum.
Steps:
Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use a constant amount of additional space.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def reverseList(self, head):
8 prev = None
9 current = head
10 while current:
11 nxt = current.next
12 current.next = prev
13 prev = current
14 current = nxt
15 return prev
16
17 def pairSum(self, head):
18 slow = fast = head
19 while fast and fast.next:
20 slow = slow.next
21 fast = fast.next.next
22
23 second_half = self.reverseList(slow)
24 max_twin_sum = 0
25 first_half = head
26 while second_half:
27 twin_sum = first_half.val + second_half.val
28 max_twin_sum = max(max_twin_sum, twin_sum)
29 first_half = first_half.next
30 second_half = second_half.next
31
32 return max_twin_sumThis solution in Python finds the middle of the linked list, reverses the second half, computes the twin sums, and returns the greatest twin sum found.
This approach makes use of an auxiliary array where we store the values of the linked list nodes. Once stored, we can leverage the structure of the list to easily compute twin sums using simple array indexing.
Steps:
Time Complexity: O(n).
Space Complexity: O(n), due to the auxiliary array.
An auxiliary array is used to read the linked list node values. Then, a loop calculates the twin sums through array indices and computes the maximum sum.