234.回文链表

234.回文链表

思路1：双指针

1.一次遍历记载链表的值到数组中
2.数组头尾双指针开始判定
复杂度：

时间O(n),空间O(n)
代码：

1. class Solution {
2. public:
3.     bool isPalindrome(ListNode* head) {
4.         vector<int>nums;
5.         while(head){
6.             nums.push_back(head->val);
7.             head=head->next;
8.         }
9.         int i=0;
10.         int j=nums.size()-1;
11.         while(i<=j){
12.             if(nums[i]!=nums[j])
13.             return false;
14.             i++;
15.             j--;
16.         }
17.         return true;
18.     }
19. };

复制代码

思路2:快慢指针+反转链表

1.快慢指针一次遍历到链表的中央
2.从中央开始反转链表后半部门
3.判定两段链表是否回文
复杂度：

时间O(n),空间O(1)
代码：

1. class Solution {
2. public:
3.     bool isPalindrome(ListNode* head) {
4.         ListNode* fast=head;
5.         ListNode* slow=head;
6.         while(fast->next!=nullptr&&fast->next->next!=nullptr){
7.             fast=fast->next->next;
8.             slow=slow->next;
9.         }
10.         //此时slow是前半段列表的末尾
11.         ListNode* backHead=reverse(slow->next);
12.         while(backHead!=nullptr){
13.             if(backHead->val!=head->val)
14.             return false;
15.             head=head->next;
16.             backHead=backHead->next;
17.         }
18.         return true;
19.     }
20.     ListNode* reverse(ListNode* head){
21.         ListNode* pre=nullptr;
22.         ListNode* cur=head;
23.         while(cur){
24.             ListNode* tmp=cur->next;
25.             cur->next=pre;
26.             pre=cur;
27.             cur=tmp;
28.         }
29.         return pre;
30.     }
31. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。