Search for a command to run...
Find the middle, reverse the second half, and compare values in O(n)
Find Middle (Phase 1)
slow and fast pointers set to head.
Middle & Reversal
1class Solution {2 reverseLinkedList(head) {3 let prev = null;4 let curr = head;5 while (curr !== null) {6 let nextNode = curr.next;7 curr.next = prev;8 prev = curr;9 curr = nextNode;10 }11 return prev;12 }13 14 isPalindrome(head) {15 if (head === null || head.next === null) {16 return true;17 }18 19 let slow = head;20 let fast = head;21 22 // Step 1: Find middle node23 while (fast.next !== null && fast.next.next !== null) {24 slow = slow.next;25 fast = fast.next.next;26 }27 28 // Step 2: Reverse second half29 let newHead = this.reverseLinkedList(slow.next);30 31 let first = head;32 let second = newHead;33 34 // Step 3: Compare both halves35 let isPal = true;36 while (second !== null) {37 if (first.val !== second.val) {38 isPal = false;39 break;40 }41 first = first.next;42 second = second.next;43 }44 45 // Step 4: Restore list46 this.reverseLinkedList(newHead);47 48 return isPal;49 }//slow: 1fast: 150}