Maximum Twin Sum of a Linked List - Practice Coding Problems

Maximum Twin Sum of a Linked List - Problem

In a linked list of size n, where n is even, the i^th 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.

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: Nodes (0,3) are twins with sum 5+1=6. Nodes (1,2) are twins with sum 4+2=6. Maximum is 6.

Example 2 — Different Values

$ Input: head = [4,2,2,3]

› Output: 7

💡 Note: Nodes (0,3) are twins with sum 4+3=7. Nodes (1,2) are twins with sum 2+2=4. Maximum is 7.

Example 3 — Minimum Size

$ Input: head = [1,100000]

› Output: 100001

💡 Note: Only one twin pair (0,1) with sum 1+100000=100001.

Constraints

The number of nodes in the list is in the range [2, 10⁵].
1 ≤ Node.val ≤ 10⁵
The number of nodes in the list is even.

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list [5,4,2,1] with even length

Twin Pairing

Node i pairs with node (n-1-i)

Output

Maximum twin sum is 6

Key Takeaway

🎯 Key Insight: Twin nodes are at mirrored positions - convert to array for easy access or use stack/reversal for space optimization

Asked in

M Microsoft 15 a Amazon 12 G Google 8

The key insight is understanding that twin nodes are at mirrored positions: node i pairs with node (n-1-i). The optimal approach converts the linked list to an array for easy twin access, or uses a stack/reversal technique for space optimization. Time: O(n), Space: O(n) for array conversion or O(1) for reversal approach.

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers with Reversal	O(n)	O(1)	Reverse second half, then use two pointers to find maximum twin sum
Array Conversion	O(n)	O(n)	Convert linked list to array, then find maximum twin sum
Stack Approach	O(n)	O(n/2)	Use stack to store first half, then pop while traversing second half

Two Pointers with Reversal — Algorithm Steps

Step 1: Find middle using slow/fast pointers
Step 2: Reverse second half of list
Step 3: Use two pointers to calculate twin sums

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Middle

Use slow/fast pointers to find middle

Reverse Second Half

Reverse the second half in-place

Match Twins

Use two pointers to calculate twin sums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* createNode(int val) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

struct ListNode* arrayToLinkedList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = createNode(arr[0]);
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = createNode(arr[i]);
        current = current->next;
    }
    return head;
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

int solution(struct ListNode* head) {
    // Find middle using slow/fast pointers
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // Reverse second half
    struct ListNode* secondHalf = reverseList(slow);
    
    // Calculate maximum twin sum
    int maxSum = 0;
    struct ListNode* firstHalf = head;
    struct ListNode* second = secondHalf;
    
    while (second) {
        int twinSum = firstHalf->val + second->val;
        if (twinSum > maxSum) {
            maxSum = twinSum;
        }
        firstHalf = firstHalf->next;
        second = second->next;
    }
    
    return maxSum;
}

int main() {
    char line[1000000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int arr[100000];
    int size = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    struct ListNode* head = arrayToLinkedList(arr, size);
    printf("%d\n", solution(head));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find middle, single pass to reverse, single pass to calculate sums

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for pointers

✓ Linear Space

18.5K Views

Medium Frequency

~15 min Avg. Time

825 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers with Reversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler