Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 95

while (t1 != null && t2 != null) {
if (t1.data.compareTo(t2.data) != 0) return false;
t1 = t1.next;
t2 = t2.next;
}
if (t1 != null || t2 != null) return false; //if one ended but not the other
return true;
} //end equals

3.11 Example: Palindrome
Consider the problem of determining whether a given string is a palindrome (the same when spelled forward or
backward). The following are examples of palindromes (ignoring case, punctuation, and spaces):

civic
Racecar
Madam, I'm Adam.
A man, a plan, a canal, Panama.

If all the letters were of the same case (upper or lower) and the string ( word , say) contained no spaces or
punctuation marks, we could solve the problem as follows:

compare the first and last letters
if they are different, the string is not a palindrome
if they are the same, compare the second and second to last letters
if they are different, the string is not a palindrome
if they are the same, compare the third and third to last letters

We continue until we find a nonmatching pair (and it's not a palindrome) or there are no more pairs to compare
(and it is a palindrome).
This method is efficient, but it requires us to be able to access any letter in the word directly. This is possible if the
word is stored in an array and we use a subscript to access any letter. However, if the letters of the word are stored in a
linked list, we cannot use this method since we can access the letters only sequentially.
To illustrate how linked lists may be manipulated, we will use linked lists to solve the problem using the
following idea:

1. Store the original phrase in a linked list, one character per node.

2. Create another list containing the letters only of the phrase, all converted to lowercase;

call this list1 .

3. Reverse list1 to get list2 .

4. Compare list1 with list2 , node by node, until we get a mismatch (the phrase is not a

palindrome) or we come to the end of the lists (the phrase is a palindrome).

Consider the phrase Damn Mad! ; this will be stored as follows:

head

D a m n M a d !