Palindrome Linked List easy

Problem Statement

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

Steps

1. Reverse the second half of the linked list: Find the middle of the linked list using slow and fast pointers. Reverse the linked list starting from the middle.
2. Compare the first half and the reversed second half: Iterate through the first half and the reversed second half, comparing nodes' values.
3. Return the result: If all values match, return true; otherwise, return false.

Explanation

The solution leverages the properties of a palindrome: it reads the same forwards and backward. We don't need to reverse the entire linked list; we only need to reverse the second half and compare it to the first half. Using slow and fast pointers efficiently finds the middle of the list in a single pass. The reversal of the second half is done in-place, avoiding extra space.

Code

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

function isPalindrome(head: ListNode | null): boolean {
    if (head === null || head.next === null) return true; // Empty or single-node list is a palindrome

    // Find the middle of the linked list
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse the second half of the linked list
    let prev: ListNode | null = null;
    let curr = slow;
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }

    // Compare the first half and the reversed second half
    let firstHalf = head;
    let secondHalf = prev;
    while (secondHalf !== null) {
        if (firstHalf.val !== secondHalf.val) return false;
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }

    return true;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We traverse the list multiple times, but each traversal takes linear time.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. The reversal is done in-place.