Space

Open

From Fieldwork

Scales

234. Palindrome Linked List

leetcodeeasylinked-listtwo-pointersstackrecursion

v1

You are performing one single destructive act per loop. Everything else is just shuffling your feet to get ready for the next one.

The trick is that we don't create new nodes. We just take the existing nodes in the second half of the list and flip their arrows ($next$ pointers) to point backward.

The Algorithm:

Find the Middle: Use two pointers, Slow (moves 1 step) and Fast (moves 2 steps). When Fast hits the end, Slow is at the middle.

Reverse the Second Half: Take the list starting from slow.next and reverse the pointers in-place.

Compare: Run one pointer from the head and one from the tail (the start of the reversed half). If values match, it's a palindrome.

(Optional) Restore: Reverse the second half back to original form so you don't mess up the input list for the caller.

class Solution:
    def isPalindrome(self, head):
        if not head or not head.next:
            return True

        # 1. Find the Middle using Fast/Slow pointers
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 2. Reverse the second half in-place
        # 'prev' will eventually become the head of the reversed half
        prev = None
        curr = slow # 'slow' is roughly the middle
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            
        # 3. Compare the two halves
        left = head
        right = prev # 'prev' is now the start of the reversed right half
        
        while right: # We only check until the right half ends
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
            
        return True

v2

No content

class Solution:
    def isPalindrome(self, head):
        vals = []
        current = head
        # 1. Copy to list
        while current:
            vals.append(current.val)
            current = current.next
        
        # 2. Check if list is palindrome
        return vals == vals[::-1]

v3

When you look at the code, it looks like 4 lines of chaos. But in reality:

Lines 1, 3, and 4 are just admin work. You are updating your local variables (stack variables). You aren't touching the data structure.

Line 2 is the only actual event.

The "Surgical" View
If you imagine the Linked List as a long chain of people holding hands:

Step 1: You look at who the current person (curr) is holding hands with on the right (next). You make a mental note.

Step 2 ( The Mutation): You force curr to let go of the right hand and grab the left hand (prev).

Step 3 & 4: You physically step sideways to the next person.

The "chain" isn't exploding. You are just walking down the line, forcing one person at a time to turn around.

# 1. READ (Safe)
# We are just looking at the map and remembering where to go next.
# No structure changes.
next_temp = curr.next 

# 2. MUTATE (The "One Thing")
# This is the ONLY time we touch the heap/memory structure.
# We flip exactly one arrow.
curr.next = prev

# 3. MOVE (Safe)
# We just update our own internal label 'prev' to point to the current node.
# No structure changes.
prev = curr

# 4. MOVE (Safe)
# We update our label 'curr' to point to the saved location.
# No structure changes.
curr = next_temp

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode

leetcodeDec 2, 2025