To approach this problem, we can picture a palindrome like 0 -> 1 -> 2 -> 1

– > 0. We know that, since it’s a palindrome, the list must be the same backwards and

forwards.This leads us to our first solution.

**Solution #1: Reverse and Compare**

Our first solution is to reverse the linked list and compare the reversed list to the original

list. If they’re the same, the lists are identical.

Note that when we compare the linked list to the reversed list, we only actually need to

compare the first half of the list. If the first half of the normal list matches the first half

of the reversed list, then the second half of the normal list must match the second half

of the reversed list.

**Solution #2: Iterative Approach**

We want to detect linked lists where the front half of the list is the reverse of the second

half. How would we do that? By reversing the front half of the list. A stack can accomplish

this.

We need to push the first half of the elements onto a stack. We can do this in two

different ways, depending on whether or not we know the size of the linked list.

If we know the size of the linked list, we can iterate through the first half of the elements

in a standard for loop, pushing each element onto a stack. We must be careful, of course,

to handle the case where the length of the linked list is odd.

If we don’t know the size of the linked list, we can iterate through the linked list, using

the fast runner / slow runner technique described in the beginning of the chapter. At

each step in the loop, we push the data from the slow runner onto a stack. When the

fast runner hits the end of the list, the slow runner will have reached the middle of the

linked list. By this point, the stack will have all the elements from the front of the linked

list, but in reverse order.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
package NewLinkedList; import java.util.Stack; public class LinkedListPalindrome { private static Link currentRunner; private static Link head; public static void main(String[] args) { //Inserting Link.insert(1); Link.insert(2); Link.insert(3); Link.insert(2); Link.insert(1); Link.printList(); Link.palindrome(); } protected static class Link { private int data; private Link nextlink; public Link(int d1) { this.data = d1; } public static void palindrome() { Link currentForCount = head; Link checkPalindrome = head; boolean odd = false; Stack<Integer> stack = new Stack<Integer>(); int length = 0; int count = 0; while(currentForCount != null) { count++; currentForCount = currentForCount.nextlink; } // It will handle even and odd number of values in linked list if(count%2 == 0) { length = count/2; } else { odd = true; length = count/2 +1; } System.out.println("Length of LinkedList is "+length); // Push half number of values in stack for(int i=0; i<length;i++) { System.out.println("The data is "+checkPalindrome.data); stack.push(checkPalindrome.data); checkPalindrome = checkPalindrome.nextlink; } // remove 1 value if odd number of values present in the linked list if(odd) { stack.pop(); } // Check if the linked list has a palindrome values or not. while(checkPalindrome != null) { if(checkPalindrome.data == stack.pop()) { System.out.println("It's a palindrome"); } else { System.out.println("Not a palindrome"); } checkPalindrome = checkPalindrome.nextlink; } } public static void insert(int d1) { Link a = new Link(d1); a.nextlink = null; if (head != null) { currentRunner.nextlink = a; currentRunner = a; } else { head = a; currentRunner = a; } System.out.println("Inserted -:"+d1); } public static void printList() { System.out.println("Elements in the list are"); System.out.println("-------------------------"); Link temp = head; while (temp != null) { System.out.println(temp.data); temp = temp.nextlink; } } } } |

As Charlie Sheen says, this article is “WINGINN!”