Problem Statement
leetcode problem link
My Solution [Accepted]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def pairSum(self, head: Optional[ListNode]) -> int:
curr = head
arr = []
while curr:
arr.append(curr.val)
curr = curr.next
l, r = 0, len(arr) - 1
res = 0
while l < r:
res = max(res, arr[l] + arr[r])
l += 1
r -= 1
return res
Editorial
Approach 1: Using List Of Integers
class Solution(object):
def pairSum(self, head):
current = head
values = []
while current:
values.append(current.val)
current = current.next
i = 0
j = len(values) - 1
maximumSum = 0
while(i < j):
maximumSum = max(maximumSum, values[i] + values[j])
i = i + 1
j = j - 1
return maximumSum
Approach 2: Using Stack
class Solution(object):
def pairSum(self, head):
current = head
st = []
maximumSum = 0
while current:
st.append(current.val)
current = current.next
current = head
size = len(st)
count = 1
maximumSum = 0
while count <= size/2:
maximumSum = max(maximumSum, current.val + st.pop())
current = current.next
count = count + 1
return maximumSum
Approach 3: Reverse Second Half In Place
class Solution(object):
def pairSum(self, head):
slow, fast = head, head
maximumSum = 0
# Get middle of the linked list.
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# Reverse second half of the linked list.
curr, prev = slow, None
while curr:
curr.next, prev, curr = prev, curr, curr.next
start = head
while prev:
maximumSum = max(maximumSum, start.val + prev.val)
prev = prev.next
start = start.next
return maximumSum