Palindrome Linked List

Question: Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

You may view the full question here.

Approach: The solution can be described using the following steps —

1. Find the mid point of the list
2. Check if the first half of the list is equal to the reversed second half. (You can reverse either halves.)

Inspired by Floyd’s cycle -finding algorithm, we use two pointers — tortoise and hare to find the middle node of the linked list.

We have the following three approaches to accomplish the second step:

Approach 1: Using a StringBuilder we collect the first half of the list into a reversed String and the latter half with its order preserved, also as a String. We then compare the two and see they are equal.

//Approach 1:
//Runtime: 235ms
//Memory usage: 43.1MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null){
            return true;
        }
        ListNode mid = head;
        ListNode end = head;
        StringBuilder firstHalf = new StringBuilder();
        firstHalf.append(head.val);
        while(end!=null && end.next!=null){
            mid = mid.next;
            end = end.next.next;
            if(end!=null) {
                firstHalf = new StringBuilder().append(mid.val).append(firstHalf);
            }
        }
        
        StringBuilder secondHalf = new StringBuilder();
        while(mid!=null){
            secondHalf.append(mid.val);
            mid = mid.next;
        }
        
        return firstHalf.toString().equals(secondHalf.toString());
    }
}

Clearly, Strings / StringBuilders are not the best way to go!

Approach 2: Now, how about creating a custom class similar to ListNode, that stores the previous index instead of the next. (Of course, we could have simply used ListNode class as is. But, come on! There should have been some decent amount of effort put in to the solution. :P)

//Approach 2:
//Runtime: 2ms
//Memory usage: 39.8MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class RevListNode {
    int val;
    RevListNode prev;
    RevListNode(int x) { val = x; }
}
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null){
            return true;
        }
        
        ListNode mid = head;
        ListNode end = head;
        
        RevListNode rev = new RevListNode(head.val);
        
        while(end!=null && end.next!=null){
            mid = mid.next;
            end = end.next.next;
            
            if(end!=null){
                RevListNode curr = new RevListNode(mid.val);
                curr.prev = rev;
                rev = curr;
            }
        }
        
        while(mid!=null){
            if(mid.val!=rev.val){
                return false;
            }
            mid = mid.next;
            rev = rev.prev;
        }
        
        return rev==null;
    }
}

That’s some significant improvement in the speed.

Approach 3: Well, there is not much improvement in the performance with this approach. Although, it makes sense to leverage on the LIFO nature of Stacks.

//Approach 3:
//Runtime: 2ms
//Memory usage: 39.6MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null){
            return true;
        }
        
        Stack<Integer> stack = new Stack();
        stack.push(head.val);
        ListNode mid = head;
        ListNode end = head;
        
        while(end!=null && end.next!=null){
            mid = mid.next;
            end = end.next.next;
            
            if(end!=null){
                stack.push(mid.val);
            }
        }
        
        while(mid!=null){
            if(mid.val!=stack.pop()){
                return false;
            }
            mid = mid.next;
        }
        
        return stack.isEmpty();
    }
}

Find more posts here.

Cheers & Chao!