Given a circular single linked list and the start pointer, check if it is a palindrome

palindromelist.cpp

/**
 * Given a circular single linked list and the start pointer, check if it is a palindrome
 * use a slow/fast pointer + stack is an elegant way
 * tip: wheneve there is a circular linked list, think about using slow/fast pointer
 */

#include <iostream>
#include <stack>
using namespace std;

struct Node
{
	char c;
	Node* next;
	
	Node(char c) {this->c = c;}
	Node* chainNode(char c)
	{
		Node* p = new Node(c);
		p->next = NULL;
		this->next = p;
		return p;
	}
};

void printList(Node* pStart)
{
	Node* p = pStart;
	cout << p->c << "-";
	p = p->next;
	while(p != pStart)
	{
		cout << p->c << "-";
		p = p->next;
	}
	cout << pStart->c;
}

bool isPalindrome(Node* pStart)
{
	Node* pSlow = pStart;
	Node* pFast = pStart;
	
	stack<Node*> s;
	bool bEven = false;
	while(true)
	{
		// BUG1: check fast pointer first
		pFast = pFast->next;
		if(pFast == pStart)
		{
			bEven = false;
			break;
		}
		else
		{
			pFast = pFast->next;
			if(pFast == pStart)
			{
				bEven = true;
				break;
			}
		}
		
		pSlow = pSlow->next;
		s.push(pSlow);
		
	}
	if(s.empty()) return true; // BUG2: a, a->b->a
	if(bEven) pSlow = pSlow->next; // BUG3: a->b->c->b->a, a->b->c->d->c->b->a: jump over the center pointer
	
	while(!s.empty())
	{
		// pop stack and advance linked list
		Node* topNode = s.top();
		s.pop();
		pSlow = pSlow->next;
		
		// check
		if(topNode->c != pSlow->c)
		{
			return false;
		}
		else
		{
			if(s.empty()) return true;
		}
	}
	
	return false;
}

void test0()
{
	Node* pStart = new Node('a');
	pStart->next = pStart;
	
	cout << "test0: ";
	printList(pStart);
	cout << endl;
	cout << isPalindrome(pStart) << endl << endl;
}

void test1()
{
	Node* pStart = new Node('a');
	Node* pLast = pStart->chainNode('b');
	pLast->next = pStart;
	
	cout << "test1: ";
	printList(pStart);
	cout << endl;
	cout << isPalindrome(pStart) << endl << endl;
}

void test2()
{
	Node* pStart = new Node('a');
	Node* pLast = pStart->chainNode('b')->chainNode('b');
	pLast->next = pStart;
	
	cout << "test2: ";
	printList(pStart);
	cout << endl;
	cout << isPalindrome(pStart) << endl << endl;
}

void test3()
{
	Node* pStart = new Node('a');
	Node* pLast = pStart->chainNode('b')->chainNode('b')->chainNode('b');
	pLast->next = pStart;
	
	cout << "test3: ";
	printList(pStart);
	cout << endl;
	cout << isPalindrome(pStart) << endl << endl;
}

void test4()
{
	Node* pStart = new Node('a');
	Node* pLast = pStart->chainNode('b')->chainNode('c')->chainNode('b');
	pLast->next = pStart;
	
	cout << "test4: ";
	printList(pStart);
	cout << endl;
	cout << isPalindrome(pStart) << endl << endl;
}

void test5()
{
	Node* pStart = new Node('a');
	Node* pLast = pStart->chainNode('b')->chainNode('c')->chainNode('d');
	pLast->next = pStart;
	
	cout << "test5: ";
	printList(pStart);
	cout << endl;
	cout << isPalindrome(pStart) << endl << endl;
}

void test6()
{
	Node* pStart = new Node('a');
	Node* pLast = pStart->chainNode('b')->chainNode('c')->chainNode('d')->chainNode('c')->chainNode('b');
	pLast->next = pStart;
	
	cout << "test6: ";
	printList(pStart);
	cout << endl;
	cout << isPalindrome(pStart) << endl << endl;
}

void test7()
{
	Node* pStart = new Node('a');
	Node* pLast = pStart->chainNode('b')->chainNode('c')->chainNode('d')->chainNode('x')->chainNode('d')->chainNode('c')->chainNode('b');
	pLast->next = pStart;
	
	cout << "test7: ";
	printList(pStart);
	cout << endl;
	cout << isPalindrome(pStart) << endl << endl;
}

int main()
{
	test0();
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
	test7();
}

result.txt

$ palindromelist.exe
test0: a-a
1

test1: a-b-a
1

test2: a-b-b-a
1

test3: a-b-b-b-a
1

test4: a-b-c-b-a
1

test5: a-b-c-d-a
0

test6: a-b-c-d-c-b-a
1

test7: a-b-c-d-x-d-c-b-a
1

result.txt

$ palindromelist.exe
test0: a-a
1

test1: a-b-a
1

test2: a-b-b-a
1

test3: a-b-b-b-a
1

test4: a-b-c-b-a
1

test5: a-b-c-d-a
0

test6: a-b-c-d-c-b-a
1

test7: a-b-c-d-x-d-c-b-a
1

$ palindromelist.exe
test0: a-a
1

test1: a-b-a
1

test2: a-b-b-a
1

test3: a-b-b-b-a
1

test4: a-b-c-b-a
1

test5: a-b-c-d-a
0

test6: a-b-c-d-c-b-a
1

test7: a-b-c-d-x-d-c-b-a
1