[코딩인터뷰 완전정복] 2.6 회문

Q : 주어진 연결리스트가 회문(palindrome)인지 검사하는 함수를 작성하라.

// LinkedList.h
#include <iostream>

template <class T>
struct node {
	T data;
	node *next;
};

template <class T>
class linked_list{
private:
	node<T> *head, *tail;
public:
	linked_list() {
		head = NULL;
		tail = NULL;
	}

	node<T>* add_node(T n) {
		node<T> *temp = new node<T>;
		temp->data = n;
		temp->next = NULL;
		if (head == NULL) {
			head = temp;
			tail = temp;
		}
		else {
			tail->next = temp;
			tail = tail->next;
		}

		return temp;
	}

	void addFirst(T x) {
		node<T> *temp = new node<T>;
		temp->data = x;
		temp->next = head;
		head = temp;
		if (tail == NULL) tail = temp;

	}

	void addFirst(node<T> *node) {
		node->next = head;
		head = node;
		if (tail == NULL) tail = node;

	}

	int removeFirst() {
		if(head == NULL) return NULL;

		int data = head->data;
		head = head->next;

		return data;
	}

	node<T>* first() {
		return head;
	}

	void printLinkedList() {
		if (head == NULL) return;

		node* currentNode = head;
		while (currentNode->next != NULL) {
			printf("%d - ", currentNode->data);
			currentNode = currentNode->next;
		}
		printf("%d", currentNode->data);

		printf("\n");
	}
};

#include <iostream>
#include "LinkedList.h"

bool IsPalindrome(linked_list<char> list) {
	int length = 0;
	char *buffer;
	node<char> *pt = list.first();

	while (pt != NULL) {
		length++;
		pt = pt->next;
	}

	buffer = new char[(length-1)/2];
	pt = list.first();

	for (int i = 0; i < (length - 1) / 2; i++) {
		buffer[i] = pt->data;
		pt = pt->next;
	}

	printf("%d\n", length);
	if (length % 2 == 1) pt = pt->next;

	for (int i = (length - 3) / 2; i >= 0; i--) {
		if (buffer[i] != pt->data) return false;
		pt = pt->next;
	}

	return true;
}

int main() {
	linked_list<char> list;
	list.add_node('a');
	list.add_node('b');
	list.add_node('c');
	list.add_node('e');
	list.add_node('c');
	list.add_node('b');
	list.add_node('a');

	printf("%d\n", IsPalindrome(list));
}

리스트의 길이를 알아낸뒤 그 절반만큼의 크기를 가진 문자 배열을 생성한다.

문자열의 절반을 문자 배열에 담은 뒤 배열을 거꾸로 탐색하며 문자열의 나머지 절반과 같은지 비교한다.

 

포인터 2개를 이용하면 길이를 알아내는 과정을 생략 할 수 있다.

(포인터1은 1칸씩 순회 포인터2는 2칸씩 순회하여 포인터2가 리스트 끝에 도달하면 포인터1은 중간에 있음)