LeetCode 2130. Maximum Twin Sum of a Linked List

2130. Maximum Twin Sum of a Linked List

 

Problem

---

Solution

The key requirements of this problem are as follows:

1. The linked list has an even legnth.
2. The ith node is paired with the (length-1-i)th node.
3. Return the maximum sum among all twin pairs.

To satisfy these requirements, I used a two-pointer approach.

First, I split the problem into three steps.

1. Find the middle nodes of the list.
2. Reverse the second half of the list.
3. Compare the two halves node by node and track the maximum sum.

To find the middle, I use slow and fast pointer.

• slow starts as head and moves single step at a time.
• fast starts as head and moves two steps at a time.

When fast reaches the end, slow points to the middle of the list.

To reverse the second half, initialize three pointers.

• prev starts as None.
• rev starts as slow.
• ahead is used to store the next node during iteration.

During reverse is like below.

1. Store rev.next in ahead.
2. Change rev.next to point to prev.
3. Move prev to rev
4. Move rev to ahead.

Repeat until the second half is fully reversed.

 

After that, prev points to the head of the reversed half.

 

Now, simply compare the two halves.

 

In each iteration, add prev.val and head.val and update when result is smaller than the sum.

 

At the end of the loop, return the result.

 

 

class Solution(object):
    def pairSum(self, head):

        slow = fast = head
        result = 0

        while fast:
            fast = fast.next.next
            slow = slow.next

        prev = None
        rev = slow

        while rev:
            ahead = rev.next
            rev.next = prev
            prev = rev
            rev = ahead

        while prev:
            temp = prev.val+head.val
            if temp > result:
                result = temp
            prev = prev.next
            head = head.next

        return result 

---

 

https://github.com/K-MarkLee/LeetCode-Practice

GitHub - K-MarkLee/LeetCode-Practice: A collection of LeetCode questions to ace the coding interview! - Created using [LeetHub 2