Leetcode #234 - Palindrome Linked List

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

Method 1: Create an array of values

The structure of a linked list doesn't provide access to the total size of the list. To get around this we can iterate over the list and push the node values on to an array. At that point we have access to the array's length and can use a single pointer i to compare values opposite to eachother in the array.

var isPalindrome = function(head) {
    let values = []
    // push all node values into an array
    while (head !== null) {
        values.push(head.val)
        head = head.next
    }
    // iterate over array and compare values
    for (let i = 0; i < values.length >> 1; i++) {
        // (values.length - i - 1) is our virtual pointer
        if (values[i] !== values[values.length - i - 1]) return false
    }
    return true
};

The time and space complexity of this method are O(n)

Method 2: Reverse the Second Half in Place

We can use a fast and slow pointer to get to the center and the end of the list, respectively. Once we are able to determine the center, we use the slow pointer to re-link the second half of the list in reverse. I like to conceptualize this method as taking a snake and turning its tail into a head, resulting in a two headed snake with a tail (ListNode.next = null) in the middle.

var isPalindrome = function(head) {
    if (head === null || head.next == null) return true
    let slow = head
    let fast = head

    while (fast !== null && fast.next !== null) {
        fast = fast.next.next
        slow = slow.next
    }
    // if list length is odd, move slow over one to start
    // the second half of the list
    if (fast) {
        slow = slow.next
    }

    // reverse the second half of the list
    slow = reverse(slow)
    fast = head

    // check for palindromicity
    while (slow) {
        if (slow.val !== fast.val) {
            return false
        }
        slow = slow.next
        fast = fast.next
    }
    return true
}

function reverse(head) {
    let prev = null
    let next;
    while (head) {
        next = head.next
        head.next = prev
        prev = head
        head = next
    }
    return prev
}

The time complexity is O(n) and space complexity is O(1) as we are not creating any extra arrays.

Comments

[Sebastian Leukhin]

This code is difficult to understand. Variable names, especially when goes like this: fast = head, and expressions like reverse(slow).
I think it would better to go to the end saving the prev node to prev property and when you achieve the end, you can just compare head and last.prev and go ahead until node links are the same. What do you think about it?