Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Fast & Slow Pointers

Guide 5 of 6 · Path 5 of 6

← PreviousNext →

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

Easyfast-slow-pointers

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

Tested only
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;
}

Reflection