In this tutorial, I am going to discuss a programming question Palindrome linked list and it’s implementation using java code.
Given a singly linked list, Write a code that returns true if the given linked list is a Palindrome else return false.
For example –
Example 1 –
1 -> 3 -> 4 -> 3 -> 1 -> NULL
It’s a palindrome.
Example 2 –
1 -> 3 -> 4 -> NULL
It’s not a palindrome.
NOTE: We have to solve this problem in O(n) time complexity and without using any extra space.
Palindrome Linked List
In this tutorial, I am going to discuss multiple approaches and their time complexities to solve this problem. I have also added a video tutorial at the end of this post.
Programming questions on linked list
Check If a Linked List is Palindrome or Not using Stack – Java Code
In this example, we are going to this problem using stack data structure. Stack is a last in first out (LIFO) data structure. So, the element which we push in a stack at last is the first element to be popped out.
Here are the following steps.
i) We first traverse a linked list and push all the nodes value in a stack.
ii) Then, we traverse a linked list again. We do following operations.
a) Pop the value from the stack.
b) Compare the current node value with the value popped from the stack.
iii) If all nodes value matched, then return true, else return false.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
|
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 |
//Check if linked list is palindrome in java public static boolean isPalindrome(Node head) { Node temp = head; Stack<Integer> st = new Stack<>(); //Push all nodes value in a stack while (temp != null) { st.push(temp.data); temp = temp.next; } temp = head; while (temp != null) { /* Compare current node value with the popped out value of the stack, If it's not equal then return false. */ if (temp.data != st.pop()) { return false; } temp = temp.next; } return true; } |
Check Palindrome Linked List without using Extra Space – Java
In our previous approach, we have solved this problem using extra space (additional data structure). In this example, we are going to solve this problem without using extra space.
To check palindrome linked list, we divide the linked list into two halves.
We reverse first half of the linked list and compare them with second half. If both are identical then it’s a palindrome else it’s not.
For this, we take two pointers slow and fast. We move slow pointer by one step and fast pointer by two steps. Also, we take one more pointer prev which points to reverse linked list (we only reverse first half of the linked list).
For dividing the linked list in two halves, we need do the special handling for odd length linked list. As, we don’t want the middle node as part of any lists when we are going to compare them for equality.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
|
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 |
//Check Palindrome Linked List in O(1) space complexity public static boolean checkPalindrome(Node head) { Node slow = head; Node fast = head; Node prev = null; while (fast != null && fast.next != null) { //Move by two step fast = fast.next.next; Node temp = slow; slow = slow.next; temp.next = prev; prev = temp; } //Handling for odd length linked list if (fast != null) { slow = slow.next; } while (prev != null && slow != null) { if (prev.data != slow.data) { return false; } prev = prev.next; slow = slow.next; } return prev == null && slow == null; } |
