💬 Discord
Sign In
NeetCode #306LC-234EasyLinked List
← Back to All Problems

#306 · #234 · Palindrome Linked List(回文链表)

📌 Problem Statement & Constraints

Given the head of a singly linked list, return true if it is a palindrome. Constraints: the number of nodes is in [1, 10^5], 0 <= Node.val <= 9. The follow-up asks for O(n) time and O(1) space.

💡 Core Algorithmic Approaches

  1. Three steps: find the middle, reverse the second half, then compare the two halves node by node.
  2. For an odd-length list, the middle node is shared and can be ignored; the comparison loop naturally stops when the reversed half is exhausted.
  3. This achieves O(n) time and O(1) extra space, unlike copying the values into a list.
  4. Optionally restore the list afterwards, which a tidy implementation would do.

💻 Benchmark Python3 Implementation

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 1) find the middle
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 2) reverse the second half
        prev, cur = None, slow
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        # 3) compare
        left, right = head, prev
        while right:                       # the second half is no longer than the first
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): three linear passes.
💾 Space Complexity
O(1): only pointers are used.

⚠️ Interview Pitfalls & Follow-ups

  • Copying the values into a list and using two pointers: correct and simple, but O(n) space, which the follow-up forbids.
  • Comparing the whole first half: the loop must be driven by the second (reversed) half, since it is shorter for odd lengths.
  • Forgetting the odd-length middle: it is shared between the halves but the comparison loop ignores it naturally.
  • Not restoring the list: some interviewers ask for it; it is a one-line extra reversal.