#234
Palindrome Linked List
Easy Middle + reverse second half
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a singly linked list reads the same forwards and backwards, ideally in O(1) extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does the list read the same backwards?
Why this works: find the middle, reverse the second half, compare the two halves node by node.
Example: 1 → 2 → 2 → 1
second half reversed: 1 → 2compare 1=1, 2=2 → true
✦Hints open one at a time
Find the middle with slow/fast pointers.
Reverse the second half, then compare it with the first half.
↗Approach
Find the middle, reverse from there, compare node by node until the reversed half ends. (Optionally reverse it back to restore the list.)
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; } // provided by LeetCode
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = reverse(slow); // second half reversed
for (ListNode a = head, b = second; b != null; a = a.next, b = b.next) {
if (a.val != b.val) return false;
}
return true;
}
private ListNode reverse(ListNode cur) {
ListNode prev = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}!Common mistake
Copying values into an ArrayList — correct, but O(n) space.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon