Palindrome Linked List

Problem

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

Example 1:

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

Example 2:

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

Constraints:

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

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    // reverse first half of list
    let prev = null;
    let cur = head;
    let fast = head;
    while (fast?.next) {
        fast = fast.next?.next;
        [cur.next, cur, prev] = [prev, cur.next, cur];
    }

    // get head of the two linked list halves (lst1 reversed)
    let lst1 = prev;
    let lst2 = cur;
    if (fast) { // odd list length (centre node does not need to be compared)
        lst2 = lst2.next;
    }

    // check if two halves are equal
    while (lst1 && lst2) {
        if (lst1.val !== lst2.val) {
            return false;
        }
        lst1 = lst1.next;
        lst2 = lst2.next;
    }

    return true;
};

We will reverse the first half of the linked list lst1 and compared whether it is equal to the second half of the linked list lst2. Note that if the linked list has odd length, the centre node does not need to be compared with any other node for it to be a valid palindrome, hence we ignore it (this also ensures lst1 and lst2 are exactly equal in length regardless of if there is an odd or even number of nodes in the original list).

Problem​

Solution​

Problem

Solution