Maximum Twin Sum of a Linked List

MediumLinked Listfast and slow pointers

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the head of a linked list with an **even** number of nodes n. Number the nodes 0 through n - 1 from the head. Node i and node n - 1 - i are *twins* for every 0 <= i < n / 2. The *twin sum* of a pair is the sum of the two twins' values. Return the **largest** twin sum in the list. Try to solve it in O(n) time with O(1) extra space.

Examples

Input: head = [5,4,2,1]
Output: 6
The twin pairs are (5, 1) and (4, 2), with sums 6 and 6.
Input: head = [4,2,2,3]
Output: 7
The pairs are (4, 3) = 7 and (2, 2) = 4.
Input: head = [1,100000]
Output: 100001
A two-node list has a single twin pair.

Constraints

  • `n` is even and `2 <= n <= 10^5`.
  • `1 <= Node.val <= 10^5`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More fast and slow pointers problems