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 node0
is the twin of node3
, and node1
is the twin of node2
. These are the only nodes with twins forn = 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:
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
import java.util.*;
public class MaximumTwinSum {
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
LList list=new LList();
for(int i=0;i<n;i++){
list.insertFromHead(new ListNode(scan.nextInt()));
}
GetSum gs=new GetSum();
System.out.println(gs.pairSum(list.head.next));
scan.close();
}
}
class GetSum{
public int pairSum(ListNode head) {
int n=0;
Stack<Integer> tempo=new Stack<>();
while(head!=null){
tempo.push(head.val);
head=head.next;
n++;
}
n/=2;
int[] sum=new int[n];
int max=0;
int i=0;
for(;i<n;i++){
sum[i]=tempo.pop();
}
for(int j=0;j<n;j++){
sum[--i]+=tempo.pop();
if(sum[i]>max) max=sum[i];
}
return max;
}
}
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class LList{
ListNode head;
int length;
LList(){
init();
}
private void init(){
head=new ListNode(-1,null);
length=0;
}
void insertFromHead(ListNode node){
node.next=head.next;
head.next=node;
length++;
}
}