#2130

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Maximum Twin Sum of a Linked List

Find the maximum twin sum in a linked list by manipulating pointers efficiently and leveraging stack or reversal techniques.

linked list two pointers stack

Problem Statement

Given a linked list of even length, define the twin of the ith node as the (n-1-i)th node. The twin sum is the sum of a node and its twin. Your task is to find the maximum twin sum in the linked list by efficiently pairing nodes with their twins.

Implement a function that takes the head of the linked list and returns the largest possible twin sum. Consider approaches using pointer manipulation, stacks, or partial reversal to efficiently traverse and compare twin nodes without extra full-list copies.

Examples

Example 1

Input: head = [5,4,2,1]

Output: 6

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

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

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

Solution Approach

Two-Pass Approach with Reversal

Find the middle of the linked list using slow and fast pointers. Reverse the second half of the list, then iterate through both halves simultaneously to compute twin sums. Track the maximum sum while traversing and return it.

Stack-Based Method

Push the first half of the nodes onto a stack while traversing. Continue iterating through the second half, popping elements from the stack to compute twin sums. This ensures each node is paired with its twin efficiently.

In-Place Twin Comparison

Without extra space, reverse the second half in-place and traverse both halves together. Update a variable with the maximum twin sum encountered. After computation, optionally restore the original list structure if needed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for traversing the list and computing twin sums. Space complexity is O(1) for in-place reversal or O(n/2) for the stack method. Each node is processed exactly once.

What Interviewers Usually Probe

Ask about how to pair nodes efficiently without extra full-list storage.
Look for discussions on reversing part of the list or using a stack to match twins.
Probe if candidate can handle edge cases like minimal list size and large values.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly identify twin indices and summing wrong pairs.
Modifying the list incorrectly without restoring its structure if needed.
Using unnecessary extra space or traversing nodes multiple times.

Follow-up variants

Find the minimum twin sum instead of the maximum in the linked list.
Handle odd-length lists by ignoring the middle node or pairing differently.
Compute twin sums while returning a list of all twin pairs instead of just the maximum.

FAQ

What is the maximum twin sum of a linked list pattern?

It is the largest sum obtained by pairing each node with its corresponding twin node based on index symmetry.

Can I solve this without reversing the list?

Yes, using a stack to store the first half lets you pair nodes without in-place reversal.

What is the time complexity for finding the maximum twin sum?

The process requires a single traversal of the list, resulting in O(n) time complexity.

Is extra space required for this problem?

A stack approach uses O(n/2) space, while in-place reversal uses O(1) space.

How do I handle the smallest possible linked list?

For a two-node list, the maximum twin sum is simply the sum of both nodes as they are twins.

terminal

Solution

Solution 1: Simulation

We can store the values of the nodes in the linked list into an array, then use two pointers pointing to the beginning and end of the array to calculate the twin sum for each pair of twin nodes. The maximum twin sum is the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        s = []
        while head:
            s.append(head.val)
            head = head.next
        n = len(s)
        return max(s[i] + s[-(i + 1)] for i in range(n >> 1))

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        s = []
        while head:
            s.append(head.val)
            head = head.next
        n = len(s)
        return max(s[i] + s[-(i + 1)] for i in range(n >> 1))

Continue Practicing

#2095 delete the middle node of a linked list #2000 reverse prefix of word #2289 steps to make array non decreasing