Home » Algorithm » Datastructure » Interviews » Linked List » Check linked list is palindrome or not in java

Check linked list is palindrome or not in java

in , , , - on 17:45:00 - No comments

Check linked list is palindrome or not in Java.

A palindromic number is a number that is the same when written forwards or backwards.

Lets see sample input and output for better understanding:

Algorithm 

We will see Recursive and Iterative approach to check if linked list is palindrome or not in java.

Iterative Approach using Stack:
Step 1: Iterate the linked list and put the elements in the stack.
Step 2: Iterate the linked list again and compare each element with the element on the stack.
Step 3: If the element matches then linked list is palindrome else not.

Iterative Approach using Stack Optimized way:
In the first approach, we put all the elements on the Stack, but we do not really require that.
If we put only half the list on Stack that should be good enough to test whether it is palindrome or not.

Step 1: Find the middle node of the linked list and put the half list on to Stack.
Step 2: From the middle node, continue till the end and compare it will the data on the Stack.
Step 3: If the element matches then linked list is palindrome else not.

Note: Only problem we would be having is to find the middle node in case of odd and even list.
We would find the middle node using tortoise and hare pointer, jumping hare pointer twice and tortoise one node at a time.
If fastPointer points to last element of the linked list, it means list is of odd length else of even length.
Example of odd length: 1 2 3 2 1 -> while skipping two elements, fastPointer will stop at last node.
fastPointer movement will be -> (1 then 3 and 1)

Example of even length: 1 2 2 1  -> while skipping two elements, fastPointer will stop at null node.
fastPointer movement will be -> (1 then 2 and null)


Recursive Approach:
In the Recursive approach, Iterate the linked list till the end and when the call stack returns, compare each element from the end with the start node in such a way comparing,
nth node with first node,
n-1 node with second node.,
n-2 node with third node and so on.


Java Program to Check linked list is Palindrome or not.
?
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
package com.javabypatel.linkedlist;
 
import java.util.Stack;
 
/*
    Input: 1 -> 2 -> 3 -> 2 -> 1
    Output: Palindrome
 
    Input: 1 -> 2 -> 2 -> 1
    Output: Palindrome
 
    Input: 1 -> 1
    Output: Palindrome
 
    Input: 1
    Output: Palindrome
 
    Input: 1 -> 2 -> 3 -> 1
    Output: Not Palindrome
 
 */
public class PalindromeCheck {
    LinkedListNode startNode;
    static LinkedListNode temp;
 
    public static void main(String[] args) {
        PalindromeCheck palindromeCheck = new PalindromeCheck();
        palindromeCheck.addNode(new LinkedListNode(10));
        palindromeCheck.addNode(new LinkedListNode(20));
        palindromeCheck.addNode(new LinkedListNode(10));
        palindromeCheck.addNode(new LinkedListNode(20));
        palindromeCheck.addNode(new LinkedListNode(10));
 
        //Print List
        System.out.println("Original List is: ");
        palindromeCheck.printLinkList(palindromeCheck.startNode);
        System.out.println();
 
        temp = palindromeCheck.startNode;
        boolean result = palindromeCheck.isPalindromeWithStaticPointer(palindromeCheck.startNode);
        System.out.println("Result using static way :" + result);
 
        Result res = palindromeCheck.isPalindromeWithExplicitResultType(palindromeCheck.startNode,
            palindromeCheck.startNode);
        System.out.println("Result using explicit type way :" + res.result);
 
        result = palindromeCheck.isPalindromeUsingStack(palindromeCheck.startNode);
        System.out.println("Result using Stack :" + result);
 
        result = palindromeCheck.isPalindromeUsingStackOptimized(palindromeCheck.startNode);
        System.out.println("Result using Stack optimized way:" + result);
    }
 
    //Optimized stack way, No need to put all the elements in the stack, only n/2 elements we can put in stack
    //and compare each element from that point with the head of the stack.
    private boolean isPalindromeUsingStackOptimized(LinkedListNode startNode) {
        Stack<Integer> stack = new Stack<>();
 
        //Find middle elememt
        LinkedListNode fastPointer = startNode;
        LinkedListNode slowPointer = startNode;
        while(fastPointer != null && fastPointer.getNext() != null) {
            stack.add(slowPointer.getData());
            slowPointer = slowPointer.getNext();
            fastPointer = fastPointer.getNext().getNext();
        }
 
        //If fastPointer points to last element of the linked list, it means list is of odd length else of even length.
        //Example of odd length: 1 2 3 2 1 -> while skipping two elements, fastPointer will stop at last node.
        // fastPointer movement will be -> (1 then 3 and 1)
 
        //Example of even length: 1 2 2 1  -> while skipping two elements, fastPointer will stop at null node.
        // fastPointer movement will be -> (1 then 2 and null)
        if (fastPointer != null) {
            //odd length, so remove the middle element from the stack
            slowPointer = slowPointer.getNext();
        }
 
        //slowPointer is at middle node, continue it till end and compare each element with element in stack
        while(slowPointer != null) {
            if (stack.pop() != slowPointer.getData()) {
                return false;
            }
            slowPointer = slowPointer.getNext();
        }
        return true;
    }
 
 
    private boolean isPalindromeUsingStack(LinkedListNode startNode) {
        Stack<Integer> stack = new Stack<>();
 
        LinkedListNode temp = startNode;
        while(temp != null) {
            stack.add(temp.getData());
            temp = temp.getNext();
        }
 
        while(startNode != null) {
            if (stack.pop() != startNode.getData()) {
                return false;
            }
            startNode = startNode.getNext();
        }
        return true;
    }
 
    // When we reach the end of recursive stack, we will start comparing,
    // the nth node with first node, the n-1 node with second node and so on.
    // Note: nodes from back that is n, n-1, n-2 .. nodes we can get it easily when the call stack is returned
    // but how to get first, second, third ... nodes.
    // we will be using Result class whose next variable points to startNode till the end of the list and
    // once the call stack recurse back, it proceeds with going further one node at a time and
    // state of that pointer is preserved in Result object which is returned back to the caller method.
    private Result isPalindromeWithExplicitResultType(LinkedListNode node, LinkedListNode startNode) {
        if (node == null) {
            return new Result(true, startNode);
        }
 
        Result res = isPalindromeWithExplicitResultType(node.getNext(), startNode);
        if(!res.result) {
            return res;
        }
 
        if (node.getData() != res.next.getData()) {
            return new Result(false);
        }
 
        res.next = res.next.getNext();
        return res;
    }
 
    private boolean isPalindromeWithStaticPointer(LinkedListNode node) {
        if (node == null) {
            return true;
        }
 
        boolean res = isPalindromeWithStaticPointer(node.getNext());
        if(!res) {
            return res;
        }
 
        if (temp.getData() != node.getData()) {
            return false;
        }
 
        temp = temp.getNext();
        return true;
    }
 
    private void printLinkList(LinkedListNode startNode) {
        LinkedListNode tempNode = startNode;
        while(tempNode!=null){
            System.out.print(tempNode.getData() + " ");
            tempNode = tempNode.getNext();
        }
    }
 
    private void addNode(LinkedListNode node) {
        if (startNode != null) {
            LinkedListNode tempNode = startNode;
            while (tempNode.getNext() != null) {
                tempNode = tempNode.getNext();
            }
            tempNode.setNext(node);
        } else {
            this.startNode = node;
        }
    }
}
 
class Result {
    boolean result;
    LinkedListNode next;
 
    Result (boolean result, LinkedListNode next) {
        this.result = result;
        this.next = next;
    }
 
    Result (boolean result) {
        this(result, null);
    }
}

Output:
Original List is:
10 20 10 20 10
Result using static way :true
Result using explicit type way :true
Result using Stack :true
Result using Stack optimized way:true
Categories: , , ,