Logo

Kode$word

Maximum Twin Sum of a Linked List (LeetCode 2130) — Intuition, Dry Run & Optimal Approach
Maximum Twin Sum of a Linked List (LeetCode 2130) — Intuition, Dry Run & Optimal Approach

Maximum Twin Sum of a Linked List (LeetCode 2130) — Intuition, Dry Run & Optimal Approach

Learn How to Pair Nodes Efficiently Using Fast & Slow Pointer and Reverse Technique

13 views
0
0
LeetcodeMediumLinkedListFast and Slow Pointer
Github icon

🔗 Try This Problem

Practice here:

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/

📌 Problem Overview

You are given a linked list of even length.

Each node has a twin node defined as:

  1. Node at index i → Twin is at index (n - 1 - i)

👉 Example (n = 4):

  1. Index 0 ↔ Index 3
  2. Index 1 ↔ Index 2

The twin sum is:

node[i] + node[n - 1 - i]

🎯 Goal:

Return the maximum twin sum among all such pairs.

🧠 Understanding the Problem

Let’s take a simple example:

Input: [4, 2, 2, 3]

Pairs:
4 + 3 = 7
2 + 2 = 4

👉 So the answer is:

7

💡 Intuition — How to Think About This Problem

At first glance, it feels like we need to access:

  1. First node
  2. Last node
  3. Second node
  4. Second last node

👉 This naturally suggests:

  1. Two-directional access
  2. But linked lists don’t allow backward traversal

🤔 Possible Thinking Patterns

🔹 Idea 1: Use Extra Space

  1. Store values in an array
  2. Use two pointers from both ends

✔ Works

❌ But uses extra space O(n)

🔹 Idea 2: Work Directly on Linked List (Better)

We need a way to:

  1. Reach the middle
  2. Access second half in reverse order

👉 That leads to a powerful idea:

“What if we reverse the second half of the list?”

Now we can compare:

  1. First half (forward)
  2. Second half (also forward after reversal)

🎥 Visual Intuition (Your Explanation Video)


👉 In this section, focus only on:

  1. Concept
  2. Visualization
  3. Thought process

❌ Avoid code here

✔ Build understanding

⚙️ Optimized Approach (Step-by-Step)

Step 1: Find Middle

Use two pointers:

  1. slow → moves 1 step
  2. fast → moves 2 steps

👉 When fast reaches end → slow is at middle

Step 2: Reverse Second Half

Start from:

slow.next

Reverse the list

Step 3: Compare Twin Pairs

Now:

  1. One pointer → start of list
  2. One pointer → start of reversed half

Calculate:

sum = left.val + right.val

Track maximum

🧪 Dry Run

Example:

Input: [5, 4, 2, 1]

Step 1: Find Middle

Slow → 4
Fast → End

Step 2: Reverse Second Half

Second half: 2 → 1
Reversed: 1 → 2

Step 3: Compare

5 + 1 = 6
4 + 2 = 6

✅ Maximum = 6

💻 Optimized Code (Java)

class Solution {

public ListNode reverse(ListNode head){
ListNode curr = head;
ListNode prev = null;

while(curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}

public int pairSum(ListNode head) {

ListNode slow = head;
ListNode fast = head;

// Find middle
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}

// Reverse second half
ListNode secondHalf = reverse(slow.next);

// Compare pairs
ListNode firstHalf = head;
int max = Integer.MIN_VALUE;

while(secondHalf != null){
int sum = firstHalf.val + secondHalf.val;
max = Math.max(max, sum);

firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}

return max;
}
}

⏱️ Complexity Analysis

TypeValue
Time ComplexityO(n)
Space ComplexityO(1)

🧩 Key Takeaways

  1. Linked list problems often require restructuring instead of extra space
  2. Reversing half is a powerful trick
  3. Fast & slow pointer is essential for mid-finding

🏁 Final Thoughts

This problem is a perfect example of:

  1. Combining multiple concepts
  2. Optimizing space
  3. Thinking beyond direct access

👉 Once you understand this pattern, many linked list problems become easier.

Related Articles

Find Length of Loop in Linked List — Complete Guide with Intuition, Dry Run & Floyd’s Cycle Algorithm

Find Length of Loop in Linked List — Complete Guide with Intuition, Dry Run & Floyd’s Cycle Algorithm

Detect Loop and Calculate Its Length Efficiently Using Fast & Slow Pointer Technique

Read Article
LeetCode 2095. Delete the Middle Node of a Linked List – Fast and Slow Pointer Approach

LeetCode 2095. Delete the Middle Node of a Linked List – Fast and Slow Pointer Approach

A Complete Guide with Intuition, Detailed Dry Run, and Optimal Solution in O(n) Time

Read Article
Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

Stop Counting Twice! Learn the Two-Pointer Trick to Remove Nodes Efficiently from the End of a Linked List

Read Article
Reverse Linked List (LeetCode 206) – The One Trick That Changes Everything

Reverse Linked List (LeetCode 206) – The One Trick That Changes Everything

From Confusion to Clarity: Master Linked List Reversal with Intuition, Visualization, and Clean Logic

Read Article

Ai Assistant Kas