Twin Sum Peak

MediumLinked List

Problem

A linked list has an even number of nodes n. Node i and node n - 1 - i (0-based) are twins: the first and the last, the second and the second-to-last, and so on.

Given the head, return the largest sum of a node's value and its twin's value. Use O(1) extra space.

Example 1

Input:
head = [4, 2, 2, 3]
Output:
7

Twin sums are 4 + 3 = 7 and 2 + 2 = 4; the largest is 7.

Example 2

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

Constraints

  • 2 ≤ number of nodes ≤ 10^5
  • The number of nodes is even.
  • 1 ≤ node.val ≤ 10^5

Hint

Show the first hint

Twins pair the first half with the second half read backwards.

Walkthrough

How to approach it

01Clarify before coding

  • Is the length always even? Yes, so every node has exactly one twin.
  • Can I copy values into an array? It works, but the target is O(1) extra space.
  • Can I modify the list? Yes for this problem.

02Brute force

Copy the values into an array and compute max(arr[i] + arr[n - 1 - i]) over the first half.

Cost: O(n) time and O(n) extra space.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.