I simply traverse the linked list and skip all the next elements which have same value;

I simply do the preorder and at any point, if no element is printed at that level then I print that element. Its quite a standard question.

Its a typical 2D dp problem, for string(i,...j) to be palindrome string[i]=string[j] and string(i+1...j-1) should be palindrome. Like how we can break the problems in smaller parts and find the longest palindromic substring by applying 2D DP. I just make him understand my approach and he was out of time, so he finishes the interview there and he was satisfied with my approach.