234.回文链表
234.回文链表思路1：双指针
1.一次遍历记载链表的值到数组中
2.数组头尾双指针开始判定
复杂度：
时间O(n),空间O(n)
代码：
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int>nums;
while(head){
nums.push_back(head->val);
head=head->next;
}
int i=0;
int j=nums.size()-1;
while(i<=j){
if(nums!=nums)
return false;
i++;
j--;
}
return true;
}
};
思路2:快慢指针+反转链表
1.快慢指针一次遍历到链表的中央
2.从中央开始反转链表后半部门
3.判定两段链表是否回文
复杂度：
时间O(n),空间O(1)
代码：
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* fast=head;
ListNode* slow=head;
while(fast->next!=nullptr&&fast->next->next!=nullptr){
fast=fast->next->next;
slow=slow->next;
}
//此时slow是前半段列表的末尾
ListNode* backHead=reverse(slow->next);
while(backHead!=nullptr){
if(backHead->val!=head->val)
return false;
head=head->next;
backHead=backHead->next;
}
return true;
}
ListNode* reverse(ListNode* head){
ListNode* pre=nullptr;
ListNode* cur=head;
while(cur){
ListNode* tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]