Leetcode234-回文链表(2019 408源题)
2019-01-10 本文已影响0人
小豆oo
题目：Leetcode234
解答：
基本思路：快慢指针找到中间结点+反转后半部分的链表
方法一：
bool isPalindrome(ListNode* head) {
//找中间结点
if(head == NULL || head->next == NULL) return true;//空结点也算回文链表
ListNode* mid = head;
ListNode* post = head;
while(post->next != NULL && post->next->next != NULL)//while两个条件用&&
{
mid = mid->next;
post = post->next->next;
}
//反转链表再比较
mid->next = reverseList(mid->next);
mid = mid->next;
while(mid!=NULL){
if(head->val == mid->val)
{
head = head->next;
mid = mid->next;
}else{
return false;
}
}
return true;
}
ListNode* reverseList(ListNode* head)
{
if(head == nullptr) return nullptr;
ListNode* pre = nullptr;
ListNode* post = head;
while(head!=nullptr)
{
post = head->next;
head->next = pre;
pre = head;
head = post;
}
return pre;
}
时间复杂度：n；空间复杂度：1
16ms；-2.39%
方法二：递归解法——利用✨递归栈“先进后出”的特性来实现一个指针从后先前一个指针从前向后进行比较
ListNode* temp;
bool isPalindrome(ListNode* head) {
temp = head;
return check(head);
}
bool check(ListNode* p)
{
if(p==nullptr) return true;//利用&的短路特性
bool isPal = check(p->next) & (temp->val == p->val);//递归
temp = temp->next;
return isPal;
}
