Posts Palindrome LinkedList
Post
Cancel

Palindrome LinkedList

PROBLEM DESCRIPTION

Given the head of a singly linked list, return true if it is a palindrome. Palindrome LinkedList

SOLUTION

Using Stack (O(n) space complexity)

snapshot

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
class Solution {
    public boolean isPalindrome(ListNode head) {
        
        int length=0;
        ListNode temp=head;
        
        while(temp!=null){
            length++;
            temp=temp.next;
        }
        
        boolean skip = (length%2==1?true:false);
        
        Stack s = new Stack();
        
        temp=head;
        
        for(int i=0;i<length;i++){
            
            if(skip && i==(length/2)){
                temp=temp.next;
                continue;
            }
            
            if(i<(length/2)){
                s.push(temp.val);
            }else{
                
                if(!s.empty()){
                    if((int)s.peek() == temp.val){
                        s.pop();
                    }else{
                        return false;
                    }
                }
                
            }
            
            temp = temp.next;
        
        }
        
        return s.empty();
        
    }
}

Optimized Approach (O(1) space complexity)

  • Reverse 2nd half of the LinkedList
  • Compare and check if elements match
  • Reverse it back again so that we don’t modify the given LinkedList
This post is licensed under CC BY 4.0 by the author.