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 the maximum twin sum of the linked list.

Examples

Example 1

graph LR
    E(5):::blue --> D(4):::red --> B(2):::red --> A(1):::blue
    
    classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff;
    classDef blue fill:#87CEEB,stroke:#333,stroke-width:2px;
  
1
2
3
4
5
6
7

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

graph LR
    D(4):::blue --> B1(2):::red --> B2(2):::red --> C(3):::blue
    
    classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff;
    classDef blue fill:#87CEEB,stroke:#333,stroke-width:2px;
  
1
2
3
4
5
6
7

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

graph LR
    A(1) --> B1(100000)
  
1
2
3
4

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, 10^5].
  • 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

  1. Use slow and fast pointers to find the middle of the list.
  2. Reverse the second half of the list.
  3. Traverse both halves in parallel, summing corresponding node values.
  4. 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.

Code

 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
}
 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;
    }
}
 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
    }
}
 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
 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
    }
}
 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
    }
}