Given the head of a singly linked list, return true if its values read the same forwards and backwards. Can you do it in O(n) time and O(1) extra space?
- The list has 1 to 10^5 nodes
- 0 <= Node.val <= 9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The easy way copies values into an array (or pushes them on a stack) and compares from both ends: O(n) time and O(n) space. To use O(1) space, we make the list itself readable from the back. Find the middle with slow and fast pointers, reverse the second half, and walk one pointer from the head and one from the new head of the reversed half, comparing values. Reversing back afterwards restores the input, which interviewers appreciate.
Algorithm
- Use slow and fast pointers to find the end of the first half (first middle).
- Reverse the list that starts at
firstHalfEnd.next. - Walk
p1fromheadandp2from the reversed half whilep2is not null; if any values differ, the answer is false. - Reverse the second half again and reattach it to restore the list.
- Return the answer.
O(n)Space: O(1)class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: def reverse(node): prev = None while node: nxt = node.next node.next = prev prev = node node = nxt return prevΒ # 1. find the end of the first half (first middle) slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next # 2. reverse the second half second = reverse(slow.next) # 3. compare both halves ok = True p1, p2 = head, second while p2: if p1.val != p2.val: ok = False break p1, p2 = p1.next, p2.next # 4. restore the list slow.next = reverse(second) return ok