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;}
};