Linked List· 25 min

Maximum Twin Sum of a Linked List

LeetCode #2130 · Medium · Interactive step-by-step visualization

Setup

Example inputhead = [5, 4, 2, 1]
Step 1 / 8

Current step

1 / 8

Pair each node with its twin. Node i is twinned with node n-1-i, but a singly linked list cannot walk backwards. Push the first half onto a stack so the second half can be paired against it.

Step log

head

head
5
4
2
1
null

First-half stack · top on right

list

5 → 4 → 2 → 1

best

0

Named pointer
Active node
Committed or completed
Detached or removed
maximum-twin-sum-of-a-linked-list.java
1public int pairSum(ListNode head) {
2    Deque<Integer> stack = new ArrayDeque<>();
3    ListNode slow = head, fast = head;
4    while (fast != null) {
5        stack.push(slow.val);
6        slow = slow.next;
7        fast = fast.next.next;
8    }
9    int best = 0;
10    while (slow != null) {
11        best = Math.max(best, slow.val + stack.pop());
12        slow = slow.next;
13    }
14    return best;
15}
● Java
Time
O(n)
Space
O(n)
Pattern
linked list
Frames
8
32 / 75