Description

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

1Input: head = [1,2,2,1]
2Output: true

Example 2:

1Input: head = [1,2]
2Output: false

Constraints:

  • The number of nodes in the list is in the range [1, 10^5].
  • 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Solution

This problem can be solved using ArrayList. We can iterate through the given list and store its elements into an ArrayList. Next, we iterate through this ArrayList in reverse and store its values in another array list. Next, we iterate through array list comparing elements of first list with reversed list. If any element does not match then the list is not palindome else at the end of the iteration, we do not have any non-matching number and the list is palindrome. This is the intuitive solution but takes 3n time complexity and requires 2n space for two ArrayLists.

Using Fast and Slow Pointers

The better approach would be to compare first half of the list with second half. In order to do that, we have to first find the middle of the list and reverse the second half of the list. Next, we compare the reversed half with the first half checking for any non-matching numbers.

 1class Solution {
 2    public boolean isPalindrome(ListNode head) {
 3        if (head == null) return true;
 4        ListNode slow = head, fast = head;
 5        while (fast != null && fast.next != null) {
 6            slow = slow.next;
 7            fast = fast.next.next;
 8        }
 9        ListNode prev = null, current = slow, next;
10        while (current != null) {
11            next = current.next;
12            current.next = prev;
13            prev = current;
14            current = next;
15        }
16        // We have broken the original list after the middle node
17        ListNode left = head, right = prev; // alternatively we could use head and prev instead of left and right
18        while (right != null) {
19            if (left.val != right.val) return false;
20            left = left.next;
21            right = right.next;
22        }
23        // Below gives error NullPointerException because list is broken at the middle after reversing
24//        System.out.println(head.val + " " + head.next.val + " " + head.next.next.val + " " + head.next.next.next.val);
25        return true;
26    }
27}
  • Time Complexity: O(n)
  • Space Complexity: O(1)