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():
  def maxLinkedList(self,head):
    if not head:
      return 0
    res = 1
    next = prev = None
    curr = head

    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():
  head = ListNode(1)
  print solution().maxLinkedList(head)

if __name__=='__main__':
  main()