Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
Could you do it in O(n) time and O(1) space?
Solution:
You have to change the structure of the linked list to have a O(n) time and O(1) space algorithm. Idea: locate the middle node of the list, reverse the first half of the list. This is not easy at all, need to be very careful when counting steps.
Round 2 solution:
No comments:
Post a Comment