"Programming is the art of algorithm design and the craft of debugging errant code.
~ Ellen Ullman
Is Linked List A Palindrome?
Dear reader, I hope you are enjoying solving these problems. This is a very nice problem, but before looking into this problem I would insist you solve the reverse data recursive. Because we will be using a similar approach.
You are given a partially written LinkedList class.
You are required to complete the body of IsPalindrome function. The function is expected to check if the linked list is a palindrome or not and return true or false accordingly.
Input and Output are managed for you.
If you face any difficulty understanding the problem, watch the Question video.
Approach :
In a normal linked list, we cannot access the first and the last, the second and the second last element at the same time. If we use a function like getNodeAt() it will take O(n) and thereby make the entire algorithm quadratic. So, what should we rather do?
We can keep two variables, left and right. Left will be in the heap, while right will be passed through the stack. Now, how do we pass elements through the stack? Yes, by using a recursive function.
Let's look at pseudocode:
Pseudocode
we will call this function as IsPalindromeHelper(head) i.e pass head to right initially. Let's look at the stack for this function. Also remember we have a global variable called left.
Analysis:
Let's assume the linked list is like this:
Now, let's say we initialize left with head. So there will be the corresponding data in the heap. Also when we call the function isPalindromeHelper(head) the param i.e right will be stored on the heap. So it will look like this:
Now this function will return again and call the isPalindromeHelper(right.next) i.e 6k will be passed.
Now this function will be called isPalindromeHelper(7k) and so on. We will keep doing this until we reach the base case. So it will look like this:
Now that we reach the base case it will return true.
At this point if you look left is pointing to the first node and the right is pointing to the last node. Now after this function returns the top of the stack will again be popped and our right will become 8k. So, to maintain congruence we have to increment left to point to its next i.e 6k. Now, the left will point to the second node, and the right will point to the second from the last node.
Clearly, we are seeing a pattern. This way we can have the pointer left to move from left to right and the pointer right-pointing from right to left. Isn't it an amazing trick?
Now to check palindromes, all we need to do is see if the left and right values are the same or not. If they are not the same we will return false. Else we will return true.
Also, if the result from the recursive call is false, which means somewhere the data didn't match then we will directly return false.
Let's come back to our example. Now the value at right i.e 9k is 10 and that of left i.e 5k is also 10, so we will return true.
We can continue this way. If you faced any doubt in this part watch the solution video.
You can try to code this taking help from the pseudocode above:
import java.io.*;
import java.util.*;
public class Main {
public static class Node {
int data;
Node next;
}
public static class LinkedList {
Node head;
Node tail;
int size;
void addLast(int val) {
Node temp = new Node();
temp.data = val;
temp.next = null;
if (size == 0) {
head = tail = temp;
} else {
tail.next = temp;
tail = temp;
}
size++;
}
public int size() {
return size;
}
public void display() {
for (Node temp = head; temp != null; temp = temp.next) {
System.out.print(temp.data + " ");
}
System.out.println();
}
public void removeFirst() {
if (size == 0) {
System.out.println("List is empty");
} else if (size == 1) {
head = tail = null;
size = 0;
} else {
head = head.next;
size--;
}
}
public int getFirst() {
if (size == 0) {
System.out.println("List is empty");
return -1;
} else {
return head.data;
}
}
public int getLast() {
if (size == 0) {
System.out.println("List is empty");
return -1;
} else {
return tail.data;
}
}
public int getAt(int idx) {
if (size == 0) {
System.out.println("List is empty");
return -1;
} else if (idx < 0 || idx >= size) {
System.out.println("Invalid arguments");
return -1;
} else {
Node temp = head;
for (int i = 0; i < idx; i++) {
temp = temp.next;
}
return temp.data;
}
}
public void addFirst(int val) {
Node temp = new Node();
temp.data = val;
temp.next = head;
head = temp;
if (size == 0) {
tail = temp;
}
size++;
}
public void addAt(int idx, int val) {
if (idx < 0 || idx > size) {
System.out.println("Invalid arguments");
} else if (idx == 0) {
addFirst(val);
} else if (idx == size) {
addLast(val);
} else {
Node node = new Node();
node.data = val;
Node temp = head;
for (int i = 0; i < idx - 1; i++) {
temp = temp.next;
}
node.next = temp.next;
temp.next = node;
size++;
}
}
public void removeLast() {
if (size == 0) {
System.out.println("List is empty");
} else if (size == 1) {
head = tail = null;
size = 0;
} else {
Node temp = head;
for (int i = 0; i < size - 2; i++) {
temp = temp.next;
}
tail = temp;
tail.next = null;
size--;
}
}
public void removeAt(int idx) {
if (idx < 0 || idx >= size) {
System.out.println("Invalid arguments");
} else if (idx == 0) {
removeFirst();
} else if (idx == size - 1) {
removeLast();
} else {
Node temp = head;
for (int i = 0; i < idx - 1; i++) {
temp = temp.next;
}
temp.next = temp.next.next;
size--;
}
}
private Node getNodeAt(int idx) {
Node temp = head;
for (int i = 0; i < idx; i++) {
temp = temp.next;
}
return temp;
}
public void reverseDI() {
int li = 0;
int ri = size - 1;
while (li < ri) {
Node left = getNodeAt(li);
Node right = getNodeAt(ri);
int temp = left.data;
left.data = right.data;
right.data = temp;
li++;
ri--;
}
}
public void reversePI() {
if (size <= 1) {
return;
}
Node prev = null;
Node curr = head;
while (curr != null) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
Node temp = head;
head = tail;
tail = temp;
}
public int kthFromLast(int k) {
Node slow = head;
Node fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast != tail) {
slow = slow.next;
fast = fast.next;
}
return slow.data;
}
public int mid() {
Node f = head;
Node s = head;
while (f.next != null && f.next.next != null) {
f = f.next.next;
s = s.next;
}
return s.data;
}
public static LinkedList mergeTwoSortedLists(LinkedList l1, LinkedList l2) {
LinkedList ml = new LinkedList();
Node one = l1.head;
Node two = l2.head;
while (one != null && two != null) {
if (one.data < two.data) {
ml.addLast(one.data);
one = one.next;
} else {
ml.addLast(two.data);
two = two.next;
}
}
while (one != null) {
ml.addLast(one.data);
one = one.next;
}
while (two != null) {
ml.addLast(two.data);
two = two.next;
}
return ml;
}
public static Node midNode(Node head, Node tail) {
Node f = head;
Node s = head;
while (f != tail && f.next != tail) {
f = f.next.next;
s = s.next;
}
return s;
}
public static LinkedList mergeSort(Node head, Node tail) {
if (head == tail) {
LinkedList br = new LinkedList();
br.addLast(head.data);
return br;
}
Node mid = midNode(head, tail);
LinkedList fsh = mergeSort(head, mid);
LinkedList ssh = mergeSort(mid.next, tail);
LinkedList sl = mergeTwoSortedLists(fsh, ssh);
return sl;
}
public void removeDuplicates() {
LinkedList res = new LinkedList();
while (this.size() > 0) {
int val = this.getFirst();
this.removeFirst();
if (res.size() == 0 || val != res.tail.data) {
res.addLast(val);
}
}
this.head = res.head;
this.tail = res.tail;
this.size = res.size;
}
public void oddEven() {
LinkedList odd = new LinkedList();
LinkedList even = new LinkedList();
while (this.size > 0) {
int val = this.getFirst();
this.removeFirst();
if (val % 2 == 0) {
even.addLast(val);
} else {
odd.addLast(val);
}
}
if (odd.size > 0 && even.size > 0) {
odd.tail.next = even.head;
this.head = odd.head;
this.tail = even.tail;
this.size = odd.size + even.size;
} else if (odd.size > 0) {
this.head = odd.head;
this.tail = odd.tail;
this.size = odd.size;
} else if (even.size > 0) {
this.head = even.head;
this.tail = even.tail;
this.size = even.size;
}
}
public void kReverse(int k) {
LinkedList prev = null;
while (this.size > 0) {
LinkedList curr = new LinkedList();
if (this.size >= k) {
for (int i = 0; i < k; i++) {
int val = this.getFirst();
this.removeFirst();
curr.addFirst(val);
}
} else {
int sz = this.size;
for (int i = 0; i < sz; i++) {
int val = this.getFirst();
this.removeFirst();
curr.addLast(val);
}
}
if (prev == null) {
prev = curr;
} else {
prev.tail.next = curr.head;
prev.tail = curr.tail;
prev.size += curr.size;
}
}
this.head = prev.head;
this.tail = prev.tail;
this.size = prev.size;
}
private void displayReverseHelper(Node node) {
if (node == null) {
return;
}
displayReverseHelper(node.next);
System.out.print(node.data + " ");
}
public void displayReverse() {
displayReverseHelper(head);
System.out.println();
}
private void reversePRHelper(Node node) {
if (node == tail) {
return;
}
reversePRHelper(node.next);
node.next.next = node;
}
public void reversePR() {
reversePRHelper(head);
Node temp = head;
head = tail;
tail = temp;
tail.next = null;
}
private boolean IsPalindromeHelper(Node right){
if(right == null){
return true;
}
boolean rres = IsPalindromeHelper(right.next);
if(rres == false){
return false;
}else if(right.data != pleft.data){
return false;
}
pleft = pleft.next;
return true;
}
Node pleft;
public boolean IsPalindrome() {
// write your code here
pleft = head;
return IsPalindromeHelper(head);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n1 = Integer.parseInt(br.readLine());
LinkedList l1 = new LinkedList();
String[] values1 = br.readLine().split(" ");
for (int i = 0; i < n1; i++) {
int d = Integer.parseInt(values1[i]);
l1.addLast(d);
}
System.out.println(l1.IsPalindrome());
}
}
java;
true";
Analysis:
Time Complexity:
This is an O(n) solution because all you need to do is look at the recursive stack. How many items/nodes do you see? Yes. n items where n is the size of the linked list.
And in each recursive call, we are doing constant-time operations. So it will be O(n).
Space Complexity:
Even though we are not using any auxiliary space, we are using the run-time stack n times to store the params of the recursive function. So it will be O(n) as well.
I hope you have understood the problem and the explanation. If you have some doubts I would insist you watch the solution video. And try to dry run the code, this will make everything clear. See you in the next problem.
