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.
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
Solution 1
1 2 3 4 5 6 7 8 910111213
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defpairSum(self,head:Optional[ListNode])->int:s=[]whilehead:s.append(head.val)head=head.nextn=len(s)returnmax(s[i]+s[-(i+1)]foriinrange(n>>1))
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcpairSum(head*ListNode)int{vars[]intfor;head!=nil;head=head.Next{s=append(s,head.Val)}ans,n:=0,len(s)fori:=0;i<(n>>1);i++{ifans<s[i]+s[n-i-1]{ans=s[i]+s[n-i-1]}}returnans}
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcpairSum(head*ListNode)int{reverse:=func(head*ListNode)*ListNode{dummy:=&ListNode{}curr:=headforcurr!=nil{next:=curr.Nextcurr.Next=dummy.Nextdummy.Next=currcurr=next}returndummy.Next}slow,fast:=head,head.Nextforfast!=nil&&fast.Next!=nil{slow,fast=slow.Next,fast.Next.Next}pa:=headq:=slow.Nextslow.Next=nilpb:=reverse(q)ans:=0forpa!=nil{ans=max(ans,pa.Val+pb.Val)pa=pa.Nextpb=pb.Next}returnans}