Problem statement:
Given a singly linked list, determine if it a palindrome.
Example:
Input: 1-> 2-> 3-> 2-> 1
Output: True
Description:
Palindrome is a word, number or sequence of characters which reads the same backward or forward. Words like noon, level or number like 12321, 161 are examples of palindrome.
We will check if given linked list is a palindrome using two approaches, one using stack and another by reversing half linked list.
1.Using stack:
Using stack, one way is to traverse entire linked list from head to tail and push each visited node on to stack. When entire linked list is traversed, start traversing linked list again from head and for each node check if node’s value matches to the stack pop node. If not, then return false.
Instead of pushing entire linked list on stack, lets push half linked list on stack and then as we continue to traverse linked list from middle node to tail, we will check for each node if node’s value is equal to stack pop value. If values are not equal then given linked list is not a palindrome.
|
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 |
private boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; Stack<ListNode> stack = new Stack<ListNode>(); ListNode slow = head; ListNode fast = head; ListNode prev = null; while(fast != null && fast.next != null) { prev = slow; stack.push(prev); slow = slow.next; fast = fast.next.next; } if(fast != null) slow = slow.next; while(slow !=null) { if(slow.val != stack.pop().val) return false; slow = slow.next; } return true; } |
For this approach time complexity is O(n) as entire linked list is traversed.Stack is used for maintaining previous nodes, so extra space required is n/2, by ignoring constant for large linked list, space complexity will be O(n) .
2. By reversing second half of linked list:
In this approach following steps will be followed.
- Traverse linked list from head to middle of linked list.
- Next step, is to divide linked list in two parts. One from head to middle and another from middle to tail of linked list.
- Reverse second linked list.
- Traverse and compare both linked list from head to tail.
- If both lists are identical, given linked list is palindrome else 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 |
public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode slow = head; ListNode fast = head; ListNode prev = null; while(fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } if(fast != null) { prev = slow; slow = slow.next; } prev.next = null; //Break linked list in two parts slow = reverse(slow); prev = head; while(slow != null) { if(prev.val != slow.val) return false; slow = slow.next; prev = prev.next; } return true; } public ListNode reverse(ListNode head){ ListNode prev = null; while(head != null) { ListNode nextNode = head.next; head.next = prev; prev = head; head = nextNode; } return prev; } |
In this approach linked list is traversed only once so time complexity will be O(n) and as constant space is required to store temporary ListNode values, space complexity will be constant, O(1).