设计一个函数判断一个链表是否为回文链表。
样例
样例 1:
输入: 1->2->1 输出: true
样例 2:
输入: 2->2->1 输出: false
bool isPalindrome(ListNode *head) {
// write your code here
vector
while(nullptr != head)
{
vec.push_back(head->val);
head=head->next;
}
bool ret=false;
//从中间向两边检验
int mid = vec.size()/2;
int end = vec.size();
if(end %2 == 0)
{
int left =mid-1;
int right = mid;
while(left>=0 && right < end)
{
if(vec[left] != vec[right])
{
return false;
}
left--;
right++;
}
}
else
{
int left =mid-1;
int right = mid+1;
while(left>=0 && right < end)
{
if(vec[left] != vec[right])
{
return false;
}
left--;
right++;
}
}
return true;
}
挑战
时间复杂度O(n)，空间复杂度O(1)。
