CC150 2.7

2_7.cpp

/* CC150 2.7
 * Implement a function to check if a linked list is a palindrome.
 */

#include <iostream>
#include <list>
#include <stack>

using namespace std;

bool isPalindrome(list<char> clst)
{
	list<char> rlst;
	for (auto c : clst)
		rlst.push_front(c);
	for (auto beg1 = clst.cbegin(), beg2 = rlst.cbegin();
		beg1 != clst.cend() && beg2 != rlst.cend(); ++beg1, ++beg2) {
		if (*beg1 != *beg2)
			return false;
	}
	return true;
}

// only need to compare the first half
// how to locate the middle? -> two iterators! runner technique
// use a stack! time: O(N); space: O(N/2).

bool isPalindrome2(list<char> clst) // empty list returns true
{
	stack<char> lstData;
	auto mid = clst.begin(), end = clst.end();
	for (auto runner = mid; runner != end; ++mid, ++runner) {
		lstData.push(*mid);
		++runner;
		if (runner == end)
			break;
	} // mid points at the center of list
	for (; mid != end; ++mid) {
		if (*mid == lstData.top()) // pop the stack if current character matches its mirror element
			lstData.pop();
		else
			return false;
	}
	return true;
/*	if (lstData.empty()) // NOT necessary since we start comparison from exactly the list center!
		return true;
	else
		return false;*/
}

int main()
{
	list<char> clst;
	char c;
	while (cin >> c)
		clst.push_back(c);
	cout << isPalindrome2(clst) << endl;
	return 0;
}