# 17.05.2023 [2130. Maximum Twin Sum of a Linked List]

17.05.2023

2130. Maximum Twin Sum of a Linked List medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/215

Problem TLDR

Max sum of head-tail twin ListNodes: a-b-c-d -> max(a+d, b+c)

Intuition

Add first half to the Stack, then pop until end reached.

Approach

• use fast and slow pointers to find the center.

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(n)

Code

        fun pairSum(head: ListNode?): Int {
            var fast = head
            var slow = head
            var sum = 0
            val stack = Stack<Int>()
                while (fast != null) {
                    stack.add(slow!!.`val`)
                    slow = slow.next
                    fast = fast.next?.next
                }
                while (slow != null) {
                    sum = maxOf(sum, stack.pop() + slow.`val`)
                    slow = slow.next
                }
                return sum
            }