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

Example 1:

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

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints:

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

Try this Problem on your own or check similar problems:

1. Palindrome Number
2. Valid Palindrome

Solution:

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) return true;
        ListNode prev = null, slow = head, fast = head;
        while(fast != null && fast.next != null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode iter1 = head, iter2 = reverseList(slow);
        while(iter1 != null && iter2 != null){
            if(iter1.val != iter2.val) return false;
            iter1 = iter1.next;
            iter2 = iter2.next;
        }
        return true;
    }

    private ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode prev = null, next = head, curr = prev;

        while(next != null){
            curr = next;
            next = next.next;
            curr.next = prev;
            prev = curr;
        }

        return prev;
    }
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

It’s obvious that we could iterate the first half of linked list and put it in a stack for example and then pop the elements and check if the value is the same when traversing the second half of the list. We get linear space complexity, but can we improve on it? We use the reverse linked list implementation from Reverse Linked List to reverse the second half of the linked list and then move simultaneously two pointers checking if the values at each are equal. One pointer (or iterator) starts from the head of the linked list, while the header points to the new head of the reversed list. If we have a match between every pair of the two halves we return true since the list is a palindrome. How do we find the middle of the list? Well we can use the slow and fast pointer method as shown in Middle of Linked List . For the sake of competition let’s do the recursive solution too:

class Solution {
    private ListNode curr;
    public boolean isPalindrome(ListNode head) {
        curr = head;
        return helper(head);
    }
    private boolean helper(ListNode head) {
        if (head == null) return true;
        boolean isPalindrome = helper(head.next) & (curr.val == head.val);
        curr = curr.next;
        return isPalindrome;
    }
}

Note that the space complexity with recursion is the same as iterative one using stack O(n).