LeetCode234_PalindromeLinkedList(返信チェーンテーブルか否か判定)c++

考え方一:
最も考えやすいのは,遍歴したノードをスタックに入れ,スタックの後進先出の特性を利用して元のチェーンテーブルと1つずつ比較することである.

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stackstack;
        ListNode *p=head;
       
         if(p==NULL||p->next==NULL)
            return true;              
        while(p){
            stack.push(p);
            p=p->next;           
        }                       
        while(!stack.empty()){
            ListNode *vall=stack.top();
            stack.pop();
            if(head->val!=vall->val)
                return false;
            head=head->next;            
        }           
        return true;        
    }
};
//    head->next!=NULL    head=head->next，     

考え方2
実は2つの考え方ではありません.ただの改善アルゴリズムです.私たちはまず半分を遍歴して、この半分をスタックの中に入れて、それからポインタを遍歴させて、この时にスタック要素と対比して、どのように半分を確定するかについては、高速ポインタを利用して、高速ポインタが最後に着いたら、遅いポインタが半分に着いて、もちろん偶数であれば、shortを前に移動させなければなりません.
fast->next->next=NULLの場合は奇数です
fast->next=NULLの場合は偶数

Stack stack=new Stack<>();
		 ListNode slow=head;
		 ListNode fast=head;
		 
		 if(fast==null||fast.next==null)//0     1   
			 return true;
 
		 stack.push(slow);
		 while(fast.next!=null&&fast.next.next!=null)
		 {
			
			 fast=fast.next.next;
			 slow=slow.next;
			 stack.push(slow);
		 }
		 if(fast.next!=null)//       
			 slow=slow.next;
		 
		 ListNode cur=slow;
		 while(cur!=null)
		 {
			 if(cur.val!=stack.pop().val)
				 return false;
			 cur=cur.next;
		 }
		 return true;

3つ目は、スローポインタを用いた逆ループチェーンテーブルの逆ループも逆出力と言えるので、チェーンテーブル自体を変えると時間が遅くなるかもしれませんが、空間が小さく、ほとんど変わりません

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return true;
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast->next!=NULL&&fast->next->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }
        slow->next=reverseList(slow->next);
        slow=slow->next;
        while(slow!=NULL){
            if(head->val!=slow->val)
                return false;
            head=head->next;
            slow=slow->next;
        }
        return true;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=NULL;
        ListNode* next=NULL;
        while(head!=NULL){
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
};