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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val=0, ListNode next=null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode ReverseList(ListNode head) {
12 ListNode prev = null;
13 ListNode current = head;
14 while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
public int PairSum(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHalf = ReverseList(slow);
int maxTwinSum = 0;
ListNode firstHalf = head;
while (secondHalf != null) {
int twinSum = firstHalf.val + secondHalf.val;
maxTwinSum = Math.Max(maxTwinSum, twinSum);
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return maxTwinSum;
}
}In C#, the solution follows reversing the second half of the list and then using two pointers to calculate the twin sums in total, delivering the largest twin sum.
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.
This solution adopts an auxiliary list to gather the values from the nodes, enabling simple index-based operations to find the maximum twin sum.