LeetCode Entry

2130. Maximum Twin Sum of a Linked List

17.05.2023 medium 2023 kotlin

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

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

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
            }