Given a linked list, find length of the longest palindrome list that exist in that linked list.
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()