Given a linked list, find length of the longest palindrome list that exist in that linked list.

Examples:

Input : List = 2->3->7->3->2->12->24 Output : 5 The longest palindrome list is 2->3->7->3->2

Input : List = 12->4->4->3->14 Output : 2 The longest palindrome list is 4->4

Brute force is approach is to generate all possible lists in O(n^2) and check if each list is a palindrome O(n). That would be a O(n^3) solution.

Another interesting approach , I came across , is that during the iterative reversal of linkedlist, at each node , we can check for the palindrome nodes by passing reversed half of the list and the rest from that node. To count nodes, it would take O(n) and iterative traversal would take O(n). It's a O(n^2) solution.

class ListNode():
def __init__(self,val):
self.val = val
self.next = None

class solution():
return 0
res = 1
next = prev = None

while curr:
next = curr.next
curr.next = prev
res = max(res, self.countNodes(curr,next) , self.countNodes(prev,next)+1)
prev = curr
curr = next
return res

def countNodes(self,start1,start2):
res = 0
while start1 and start2:
if start1.val == start2.val:
res+=1
start1 = start1.next
start2 = start2.next
else:
return 2*res
return 2*res

def main():