判斷是不是回文連結清單的方法_3種

struct TreeList{
	int val;
	TreeList*next;
	TreeList() { val = 0; next = NULL; }
	TreeList(int  a) { val = a; next = NULL; }
};


//使用棧來做，這是最簡單的方法，空間複雜度為O(n)
bool isre_1(TreeList *p) {
	stack<int>que;
	TreeList*pre = p;
	while (pre) {
		que.push(pre->val);
		pre = pre->next;
	}
	while (p) {
		if (p->val != que.top())return false;
		p = p->next;
		que.pop();
	}
	return true;

}



//使用快慢指針尋找中點，能夠比普通的暴力解法省一半的空間
bool isre_2(TreeList* p) {
	TreeList *fast = p;
	TreeList* slow = p;
	while (fast&&slow) {
		if(fast->next==NULL)
			break;
		else if(fast->next->next==NULL)
			break;
		else {
			fast = fast->next->next;
			slow = slow->next;
		}
	}
	slow = slow->next;
	stack<int>st;
	while (slow) {
		st.push(slow->val);
		slow = slow->next;
	}
	while (!st.empty()) {
		if (p->val != st.top()) {
			cout << "不是回文" << endl;
			return false;
		}
			
		else {
			p = p->next;
			st.pop();
		}
	}
	cout << "是回文" << endl;
	return true;

}




//隻是用有限幾個變量的解法，比上面的要難很多
bool isre_3(TreeList*p) {
	TreeList* fast = p;
	TreeList* slow = p;
	while (fast&&slow) {
		if (fast->next == NULL||fast->next->next==NULL)
			break;
		else {
			fast = fast->next->next;
			slow = slow->next;
		}

	}
	TreeList *mid = slow;
	TreeList *pre = slow->next;
	TreeList *after = slow;
	TreeList *temp = NULL;
	while (pre) {
		temp = pre;
		pre = pre->next;
		temp->next = after;
		after = temp;
	}
	mid->next = NULL;
	bool is = true;
	while (p&&after) {
		if (p->val != after->val) {
			is = false;
			break;
		}
		else {
			p = p->next;
			after = after->next;
		}
	}
	pre = temp->next;
	after = temp;
	after->next = NULL;
	TreeList* back = NULL;
	while (pre) {
		temp = pre;
		pre = pre->next;
		temp->next = after;
		back = after;
		after = temp;
	}
	mid->next = back;
	return is;
}