力扣打卡第二天

206. 反转链表

在这里插入图片描述

class Solution {
public:ListNode* reverseList(ListNode* head) {// //迭代法// ListNode *pre = nullptr;// ListNode *curr = head;// while(curr){//     ListNode *next = curr -> next;//     curr -> next = pre;//     pre = curr;//     curr = next;// }// return pre;//递归if(!head || !head -> next){return head;}ListNode *newhead = reverseList(head -> next);head -> next -> next = head;head -> next = nullptr;return newhead;}
};

234. 回文链表

在这里插入图片描述

1、快慢指针+翻转（可以实现进阶的要求，也就是说O(1)空间复杂度）

class Solution {
public:bool isPalindrome(ListNode* head) {if(!head || !head->next)  //表示如果head或者head->next是空的，则返回truereturn 1;ListNode *fast = head, *slow = head;ListNode *p,*pre = NULL;while(fast && fast->next){p = slow;slow = slow -> next;//慢指针fast = fast -> next ->next;//快指针p -> next = pre;//翻转pre = p;}if(fast)slow = slow -> next;//把慢指针移动到回文开始的地方while(p){if(p->val != slow->val)return 0;p = p -> next;slow = slow -> next;}return 1;}
};

2、栈

        stack<int> s; //定义栈sListNode *p = head;while(p){s.push(p -> val);//把P的值加入栈s中p = p -> next;}p = head;//把head赋值给Pwhile(p){if(p -> val != s.top()){return 0;}s.pop();//把栈上面的值pop出去p = p -> next;}return 1;