DSA sheet · Linked List · Reversal pattern

Maximum Twin Sum of a Linked List

The teacher puts this right after Palindrome Linked List on purpose: it's the same recipe, with "compare the two values" replaced by "add the two values and keep the biggest sum". We again go array → brute force with an extra list → optimal with fast & slow pointers plus reversing the second half. If you did the palindrome question, try this one on your own first.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists, fast & slow pointers and reversal from scratch
• Part A · Brute force: copy into an array, two pointers
• Part B · Optimal: middle → reverse second half → add pairs
• Part C · Revision page

Part 0 · What you must know before starting

Nodes, head, None and walking

A linked list is a chain of nodes. Each node holds a value val and a link next to the node after it. The last node points to None. We get only the head (first node), and we visit the others with a walker: curr = head, then curr = curr.next until curr is None.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

[5] → [4] → [2] → [1] → None
head

There's no index access. To reach the i-th node you follow i arrows (O(i)). And arrows go forward only: from a node you can't step back to the one before it.

Before changing any node's next, save it (nxt = curr.next). It's the only road to the rest of the list. Overwrite it unsaved and the rest is lost.

Tool 1: fast & slow pointers (the middle in one pass)

slow = fast = head
while fast and fast.next:   # fast can still jump 2
    slow = slow.next        # 1 step
    fast = fast.next.next   # 2 steps

Fast covers double the distance, so when fast hits the end, slow is halfway. For an even length like 4, fast ends on None and slow stands on the 3rd node, the first node of the second half. For an odd length, slow stands on the exact middle node.

The teacher also mentions the slower way: count the length in one pass, then walk n/2 steps in a second pass. It works but takes two passes; fast & slow does it in one.

Tool 2: reversal with prev / curr / nxt

prev = None
while curr:
    nxt = curr.next     # save
    curr.next = prev    # flip
    prev = curr         # move prev
    curr = nxt          # move curr

The first node reversed ends up pointing to None. That's what lets the right-hand walker know when to stop.

What is a "twin"?

In a list of n nodes (n even), node i and node n − 1 − i (counting from 0) are twins: the 1st and last, the 2nd and second-last, and so on. A twin sum is the sum of the two values.

Part A · Brute force: copy into an array, two pointers

LeetCode 2130

1The question in simple words

Given the head of a list with an even number of nodes, find the twin sums and return the largest one.

[5] → [4] → [2] → [1] → None    twins: 5+1 = 6, 4+2 = 6         → 6
[4] → [2] → [2] → [3] → None    twins: 4+3 = 7, 2+2 = 4         → 7
[1] → [100000] → None           twins: 1+100000 = 100001        → 100001

The teacher explains with the list 5 → 2 → 1 → 3 → 1: 5+1 = 6, 2+3 = 5, and the middle 1 has no partner. The biggest is 6. (That list has odd length, which LeetCode never gives; see Doubt 2 in Part B.)

2What the constraints tell us

• Number of nodes: even, from 2 to 10⁵ → never empty, and every node has exactly one twin.
• 10⁵ × 10⁵ = 10¹⁰ → an O(n²) idea will TLE. Her rule of thumb: past about 10⁸–10⁹ simple steps, expect TLE. So we need linear time.
• Values 1 to 10⁵ → a sum is at most 2 × 10⁵, small.
• Her usual reminder: linked-list solutions are almost always linear. Brute force = extra space or extra passes; optimal = no extra space.

3Intuition: on an array it's just two pointers

If the values were in an array, put left at the start and right at the end. Add the two, update a best variable, move left forward and right backward, repeat.

[5, 2, 1, 3, 1]
 L           R    5 + 1 = 6 → best = 6
    L     R       2 + 3 = 5 → 6 is still bigger, best stays 6
       LR         they meet → stop. Answer 6

On a linked list, right -= 1 is impossible: every node knows only the node to its right. The real fix (reverse half the list) is Part B. If you don't know that yet, the simple way out is: copy the values into an array and run the same two pointers.

4Building the logic

• Pass 1: walk the list, append each value to vals → [5, 2, 1, 3, 1].
• i = 0, j = len(vals) − 1, best = 0.
• While i < j: best = max(best, vals[i] + vals[j]), then i += 1, j -= 1.
• Why i < j? With even length the pointers cross after the last twin pair. (With odd length they'd meet at the middle, which has no twin, so we stop there too.)
• Unlike the palindrome check, there's no early exit. A later pair might have a bigger sum, so we must look at every pair.

5Approach steps

1. Copy every value into vals.
2. i, j = 0, len(vals) - 1; best = 0.
3. While i < j: update best with vals[i] + vals[j]; move i right and j left.
4. Return best.

6Code (Python)

class Solution:
    def pairSum(self, head):
        vals = []
        curr = head
        while curr:                        # copy the values out
            vals.append(curr.val)
            curr = curr.next

        i, j = 0, len(vals) - 1
        best = 0
        while i < j:                       # each twin pair once
            best = max(best, vals[i] + vals[j])
            i += 1
            j -= 1
        return best

7Code line by line

8Dry run

[4] → [2] → [2] → [3] → vals = [4, 2, 2, 3]

9Complexity & remember

• Time O(n + n/2) = O(3n/2): n to copy, n/2 rounds of the two pointers (both move each round, so they meet in the middle after n/2 rounds).
• Space O(n): the array.

Part B · Optimal: middle → reverse second half → add pairs

1The question (same), new goal

Same answer, but with O(1) extra space.

2What the constraints tell us

• At least 2 nodes → head and head.next exist, so the fast & slow loop runs at least once. No empty-list check needed.
• Even length → after fast & slow, the two halves have exactly n/2 twin pairs between them.

3Intuition: same as palindrome, add instead of compare

The teacher runs through the patterns again: basic operations (insert, delete, update) don't help. Reversal does: if the second half's arrows pointed backwards, a walker starting at the last node could move towards the middle with plain .next. That's our "right pointer". To know where the second half starts, use fast & slow (one pass instead of "count the length, then walk again").

before:  [4] → [2] → [2] → [3] → None
after:   [4] → [2] → [2] ← [3]
         left             right     ← both now move with .next

4Building the logic step by step

Step 1: fast & slow to the second half

start
[4] → [2] → [2] → [3] → None
slow/fast

move 1
[4] → [2] → [2] → [3] → None
      slow  fast

move 2
[4] → [2] → [2] → [3] → None
            slow        fast

stop: fast is None → slow = [2] (position 2), the start of the second half

Step 2: reverse from slow to the end

The piece starting at slow is [2] → [3]. Keep head untouched (it's our left pointer later).

start: prev = None, curr = slow
None   [2] → [3] → None
prev   curr

round 1: save nxt, flip curr.next (red), move prev and curr
None ← [2]   [3] → None
prev   curr  nxt
       prev  curr   ← after moving

round 2: save nxt, flip curr.next (red), move prev and curr
None ← [2] ← [3]   None
       prev  curr  nxt
             prev  curr   ← after moving

Now prev is on [3], the old last node. That's our right pointer. The whole picture:

[4] → [2] → [2] ← [3]
head         ↓    prev
            None
left's walk:  4, 2, 2      right's walk: 3, 2

Step 3: walk both, add, keep the max, stop when right is None

• Loop while right is not None. The second half ends in None because its first reversed node points to None.
• Each round: best = max(best, left.val + right.val), then left = left.next (moving right) and right = right.next (moving left).

5Approach steps

1. Fast & slow from head until fast or fast.next is None. slow = start of the second half.
2. Reverse from slow with prev / curr / nxt. prev = right pointer.
3. left = head, right = prev, best = 0.
4. While right: update best with left.val + right.val; move both one step.
5. Return best.

6Code (Python)

class Solution:
    def pairSum(self, head):
        # 1. reach the start of the second half
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. reverse the second half
        prev = None
        curr = slow
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        # 3. twin sums: head walks forward, prev walks back from the end
        best = 0
        left, right = head, prev
        while right:
            best = max(best, left.val + right.val)
            left = left.next
            right = right.next
        return best

7Code line by line

8Dry run

[4] → [2] → [2] → [3], after steps 1 and 2 drawn above (left = 1st node, right = 4th node):

Another quick check, 5 → 4 → 2 → 1: slow stops on [2]; reversed half is 1 → 2. Pairs: 5+1 = 6, 4+2 = 6 → 6 ✓. And 1 → 100000: slow stops on [100000]; one pair 1 + 100000 = 100001 ✓.

9Complexity & remember

• Middle: O(n/2) (fast jumps two). Reverse half: O(n/2). Twin sums: O(n/2). Total O(3n/2) = O(n).
• Space O(1): only pointers.
• The teacher's point: the time is the same 3n/2 as the brute force. The optimisation is purely in space, O(n) → O(1).

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

s = Solution()
print(s.pairSum(build([5, 4, 2, 1])))     # 6
print(s.pairSum(build([4, 2, 2, 3])))     # 7
print(s.pairSum(build([1, 100000])))      # 100001

Based on this video: Maximum Twin Sum of a Linked List | Reversal pattern