Palindrome Linked List
- mosesg1123
- May 2
- 4 min read
Checking whether a linked list reads the same forwards and backwards is a great warm‑up that mirrors real‑world tasks like validating undo/redo buffers or symmetric data streams. It tests your ability to manipulate list pointers and handle data in linear time and constant space.
Problem Statement
Given the head of a singly linked list, determine whether the list is a palindrome. Return true if it reads the same backwards as forwards, or false otherwise. Aim for O(n) time and O(1) extra space.
// Definition for singly-linked list:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
// Function signature in a technical interview:
public boolean isPalindrome(ListNode head);
1. Clarify Requirements Before Jumping Into Code
Can the list be empty? An empty list counts as a palindrome.
Single-node list? Also a palindrome.
Values are integers; negative or positive, but exact comparison only.
We must not modify node values; we can rewire pointers if we restore the list.
Extra space should be constant if possible; O(n) space is allowed but not ideal.
2. Identify the Category of the Question
This is a linked-list + two-pointer problem with an added in-place reversal or stack pattern. Common linked-list patterns include:
Two-pointer (fast/slow) to find mid
In-place reversal of part of the list
Dummy head for safe insertion/deletion
Stack to store node values
Recursion to simulate a stack
Recognizing “palindrome” suggests comparing mirrored halves, either via extra storage or by reversing half and then comparing.
3. Consider a Brute‑Force Approach to Understand the Problem
The simplest brute‑force: traverse the list, copy all values into an array or list, then use two indices to check whether values[i] == values[n-1-i] for all i.
Time: O(n) to collect + O(n) to compare = O(n)
Space: O(n) for the array
Pros: Very easy to implement
Cons: Uses O(n) extra memory
4. Brainstorm More Solutions
I’d like to reduce extra space. Options:
Stack of first half:
Use fast/slow to find midpoint.
Push slow’s values onto a stack while advancing fast two steps and slow one.
Then pop from stack and compare to second half.
Pros: O(n) time, O(n/2) space.
Cons: Still O(n) extra space.
What if the pointers in the second half of the linked list were reversed? Then I could traverse forward from the front pointer and backwards from the back pointer until they meet.
Reverse second half in-place:
Use fast/slow to find midpoint.
Reverse the second half of the list in-place.
Compare nodes from head and from reversed half one by one.
Restore the list by reversing the second half back.
Pros: O(n) time, O(1) space.
Cons: Pointer manipulation more complex, must restore to avoid side effects.
Recursive two-pointer:
Use recursion to traverse to end, compare on unwind with a front pointer.
Pros: Elegant code.
Cons: O(n) call stack, risk of overflow.
5. Discuss Trade‑Offs Between Your Solutions
Approach | Time | Space | Pros | Cons |
Copy to array + compare | O(n) | O(n) | Simple, minimal pointer logic | Extra O(n) memory |
Stack of first half | O(n) | O(n/2) | Simple logic, uses built-in stack | Still O(n) extra memory |
Recursive comparison | O(n) | O(n) stack | Very concise | Call stack risk, O(n) memory |
Reverse second half in-place | O(n) | O(1) | True constant space, restores original list | Pointer-reversal complexity |
Reverse-second-half is optimal for O(1) space.
6. Write Pseudocode to Structure Your Thoughts
function isPalindrome(head):
if head is null or head.next is null:
return true
// Find midpoint
slow = head
fast = head
while fast.next != null and fast.next.next != null:
slow = slow.next
fast = fast.next.next
// Reverse second half
secondHead = reverseList(slow.next)
// Compare halves
p1 = head
p2 = secondHead
result = true
while result and p2 != null:
if p1.val != p2.val:
result = false
p1 = p1.next
p2 = p2.next
// Restore list
slow.next = reverseList(secondHead)
return result
7. Consider Edge Cases
Empty list → returns true
Single node → returns true
Two equal nodes → returns true
Two different nodes → returns false
Odd length palindrome → middle node ignored correctly
Even length palindrome → splits evenly
Non-palindrome → returns false quickly on mismatch
8. Write Full Code Syntax
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// 1. Find the end of first half
ListNode firstHalfEnd = endOfFirstHalf(head);
// 2. Reverse second half
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 3. Check palindrome
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) result = false;
p1 = p1.next;
p2 = p2.next;
}
// 4. Restore list
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
9. Test Your Code
public static void main(String[] args) {
Solution sol = new Solution();
// Helper buildList(...) and toList(...) omitted for brevity
// Test 1: empty list
assert sol.isPalindrome(null) == true;
// Test 2: single node
assert sol.isPalindrome(buildList(1)) == true;
// Test 3: two-node palindrome
assert sol.isPalindrome(buildList(1,1)) == true;
// Test 4: two-node non-palindrome
assert sol.isPalindrome(buildList(1,2)) == false;
// Test 5: odd-length palindrome
assert sol.isPalindrome(buildList(1,2,3,2,1)) == true;
// Test 6: even-length palindrome
assert sol.isPalindrome(buildList(1,2,2,1)) == true;
// Test 7: complex non-palindrome
assert sol.isPalindrome(buildList(1,2,3,4,2,1)) == false;
System.out.println("All tests passed!");
}
10. Key Lessons to Remember for Future Questions
Fast/slow pointer finds the midpoint in one pass.
In‑place reversal of the second half lets you compare mirrored nodes with O(1) space.
Always restore modified data structures if the problem requires no side effects.
Brute‑force or stack solutions clarify correctness before optimizing.
Clear pseudocode separating phases (find mid, reverse, compare, restore) prevents pointer errors.
Testing both odd and even lengths, as well as trivial cases, ensures full coverage.
Good Luck and Happy Coding!
Comments