Problem#
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 themaximum twin sum of the linked list.
Examples#
Example 1#
1
2
3
4
5
6
7
8
9
10
11
12
|
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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#
1
2
3
4
5
6
7
8
9
10
|
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 <= 10^5
Solution#
Method 1 – Two Pointers and Reversal#
Intuition#
The twin sum pairs the first half of the list with the second half in reverse order. By finding the middle, reversing the second half, and pairing nodes, we can efficiently compute all twin sums and track the maximum.
Approach#
- Use slow and fast pointers to find the middle of the list.
- Reverse the second half of the list.
- Traverse both halves in parallel, summing corresponding node values.
- Track and return the maximum twin sum found.
Complexity#
- ⏰ Time complexity:
O(n) — Each node is visited a constant number of times.
- 🧺 Space complexity:
O(1) — In-place reversal, no extra space except pointers.
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public:
int pairSum(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *prev = nullptr, *cur = slow;
while (cur) {
ListNode *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
int ans = 0;
ListNode *p1 = head, *p2 = prev;
while (p2) {
ans = max(ans, p1->val + p2->val);
p1 = p1->next;
p2 = p2->next;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func pairSum(head *ListNode) int {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
var prev *ListNode
cur := slow
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
ans := 0
p1, p2 := head, prev
for p2 != nil {
if p1.Val+p2.Val > ans { ans = p1.Val + p2.Val }
p1 = p1.Next
p2 = p2.Next
}
return ans
}
|
Java#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public int pairSum(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null, cur = slow;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
int ans = 0;
ListNode p1 = head, p2 = prev;
while (p2 != null) {
ans = Math.max(ans, p1.val + p2.val);
p1 = p1.next;
p2 = p2.next;
}
return ans;
}
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
fun pairSum(head: ListNode?): Int {
var slow = head
var fast = head
while (fast != null && fast.next != null) {
slow = slow?.next
fast = fast.next.next
}
var prev: ListNode? = null
var cur = slow
while (cur != null) {
val next = cur.next
cur.next = prev
prev = cur
cur = next
}
var ans = 0
var p1 = head
var p2 = prev
while (p2 != null) {
ans = maxOf(ans, p1!!.`val` + p2.`val`)
p1 = p1.next
p2 = p2.next
}
return ans
}
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def pair_sum(head: 'ListNode') -> int:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev, cur = None, slow
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
ans = 0
p1, p2 = head, prev
while p2:
ans = max(ans, p1.val + p2.val)
p1 = p1.next
p2 = p2.next
return ans
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
impl Solution {
pub fn pair_sum(head: Option<Box<ListNode>>) -> i32 {
let mut slow = &head;
let mut fast = &head;
while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
slow = &slow.as_ref().unwrap().next;
fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
}
let mut prev = None;
let mut cur = slow.clone();
while let Some(mut node) = cur {
let next = node.next.take();
node.next = prev;
prev = Some(node);
cur = next;
}
let mut ans = 0;
let mut p1 = head;
let mut p2 = prev;
while let (Some(n1), Some(n2)) = (p1, p2) {
ans = ans.max(n1.val + n2.val);
p1 = n1.next;
p2 = n2.next;
}
ans
}
}
|
TypeScript#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
pairSum(head: ListNode | null): number {
let slow = head, fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
let prev: ListNode | null = null, cur = slow
while (cur) {
const next = cur.next
cur.next = prev
prev = cur
cur = next
}
let ans = 0, p1 = head, p2 = prev
while (p2) {
ans = Math.max(ans, p1!.val + p2.val)
p1 = p1!.next
p2 = p2.next
}
return ans
}
}
|