Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Palindrome Linked List

Problem (restated)

Return true if the linked list is a palindrome.

Intuition

Find middle, reverse second half, compare.

Approaches

Middle + reverse second half

Unverified

Time O(n)Space O(1)

Idea. Slow/fast to mid; reverse from mid.next; compare values.

Walkthrough. 1→2→2→1 is palindrome; 1→2 is not.

Trade-offs. Copying to array is O(n) space.

Solution

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null, cur = head;
  while (cur) { const n = cur.next; cur.next = prev; prev = cur; cur = n; }
  return prev;
}
export function isPalindrome(head: ListNode | null): boolean {
  if (!head || !head.next) return true;
  let slow: ListNode | null = head, fast: ListNode | null = head;
  while (fast?.next && fast.next.next) { slow = slow!.next; fast = fast.next.next; }
  let p2 = reverse(slow!.next), p1: ListNode | null = head;
  while (p2) { if (p1!.val !== p2.val) return false; p1 = p1!.next; p2 = p2.next; }
  return true;
}

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null, cur = head;
  while (cur) { const n = cur.next; cur.next = prev; prev = cur; cur = n; }
  return prev;
}
export function isPalindrome(head: ListNode | null): boolean {
  if (!head || !head.next) return true;
  let slow: ListNode | null = head, fast: ListNode | null = head;
  while (fast?.next && fast.next.next) { slow = slow!.next; fast = fast.next.next; }
  let p2 = reverse(slow!.next), p1: ListNode | null = head;
  while (p2) { if (p1!.val !== p2.val) return false; p1 = p1!.next; p2 = p2.next; }
  return true;
}

Template connection

Fast/slow to the middle, reverse the second half, compare — linked-list palindrome.

Reflection

Find the middle, reverse the second half, compare, and optionally reverse it back. Did you leave the odd middle node out of the compare?
Copying into an array is also correct. Reversing is required when the extra memory must be O(1).
Check the ends: one node is a palindrome. Two nodes may or may not be.