您的位置:首页 > 汽车 > 时评 > C++速通LeetCode简单第5题-回文链表

C++速通LeetCode简单第5题-回文链表

2024/10/31 21:21:42 来源:https://blog.csdn.net/weixin_47768406/article/details/142205025  浏览:    关键词:C++速通LeetCode简单第5题-回文链表

 

 解法1,堆栈O(n)简单法:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {stack<int> s;ListNode* cp = head;bool flag = true;while(cp!=nullptr){s.push(cp->val);cp = cp->next;}while(head!=nullptr){if(s.top()!=head->val){return false;}else{s.pop();head = head->next;}}return true;}
};

解法2, 快慢指针确定中间节点并向后逆序O(1):

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public://找到开始逆序的中间节点slowListNode* MiddleNode(ListNode* ori){ListNode* countTest = ori;ListNode* middleStart = nullptr;while(countTest!=nullptr){countTest = countTest->next;}ListNode* fast = ori;ListNode* slow = ori;//奇数偶数一样while(fast != nullptr && fast->next!= nullptr){fast = fast->next->next;slow = slow->next;}middleStart = slow;return middleStart;}//从slow的中间节点开始逆序,返回逆序后半序列的头节点ListNode* ReverseNode(ListNode* start){ListNode* pre = nullptr;ListNode* cur = start;while(cur != nullptr){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}bool isPalindrome(ListNode* head) {ListNode* rev = ReverseNode(MiddleNode(head));while(rev!=nullptr){if(rev->val!=head->val){return false;}else{head = head->next;rev = rev->next;}}return true;}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com