DSA sheet · Linked List · Reversal pattern

Palindrome Linked List

The second question of the reversal pattern. We must say whether a linked list reads the same forwards and backwards. The teacher builds the answer step by step: first the array solution with two pointers, then a brute force that copies the list into an array, and finally the optimal one that combines two patterns: fast & slow pointers to find the middle, and reversal to turn the second half around so that the "right pointer" can walk backwards. This "find middle + reverse second half + compare" recipe is reused straight away in the next problem (Maximum Twin Sum) and later in Reorder List.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists, fast & slow pointers and reversal from scratch
• Part A · Brute force: copy into an array, then two pointers
• Part B · Optimal: middle → reverse second half → compare
• Part C · Revision page

Part 0 · What you must know before starting

Nodes, head and None

A linked list is a chain of nodes. Each node holds a value (val) and a link (next) to the following node. The last node's next is None. We are only given the first node, the head.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the value in this node
        self.next = next    # the following node, or None at the end

[1] → [2] → [3] → [2] → [1] → None
head

To visit the nodes we use a walker: curr = head, then curr = curr.next again and again until curr is None. We walk with a copy so that head still marks the start.

There is no index access: to reach the i-th node you must follow i arrows from the head, which costs O(i). And the arrows only go forward. You can't step back from a node to the one before it. This one fact shapes the whole solution below.

Rule for changing arrows: save next first

A node's next is the only road to the rest of the list. If you overwrite it without saving it, everything after it is lost. So we always do nxt = curr.next before changing curr.next.

Tool 1: fast & slow pointers (finding the middle)

Two walkers start at head. slow moves 1 step at a time, fast moves 2 steps. When fast reaches the end, slow has covered half the distance, so it's standing in the middle. One pass, no counting.

slow = fast = head
while fast and fast.next:     # fast can still take 2 steps
    slow = slow.next          # 1 step
    fast = fast.next.next     # 2 steps
# slow is now the middle

• Odd length (5 nodes): fast lands on the last node, fast.next is None → stop. slow is on the exact middle (3rd node).
• Even length (4 nodes): fast jumps past the end and becomes None → stop. slow is on the second of the two middle nodes (3rd node).
• Why both checks? fast is None handles even length; fast.next is None handles odd length. Checking fast first also protects fast.next from crashing.

Tool 2: reversing a list with prev / curr / nxt (from the previous video)

prev = None
while curr:
    nxt = curr.next       # save the road ahead
    curr.next = prev      # flip the arrow backward
    prev = curr           # step prev forward
    curr = nxt            # step curr forward
# prev is the new head of the reversed piece

Remember one detail: the first node we reverse ends up pointing to None (because prev starts as None). We'll need that to know when to stop comparing.

What is a palindrome?

A sequence that reads the same from both ends: 1 2 3 2 1, 1 2 2 1, 7. The first value equals the last, the second equals the second-last, and so on. We compare the values in the nodes, not the node objects.

Part A · Brute force: copy into an array, then two pointers

LeetCode 234

1The question in simple words

Given the head of a singly linked list, return True if its values form a palindrome, else False.

[1] → [2] → [3] → [2] → [1] → None     → True   (odd length)
[1] → [2] → [2] → [1] → None           → True   (even length)
[1] → [2] → None                       → False

2What the constraints tell us

• Number of nodes: 1 to 10⁵ → the list is never empty, but it can be a single node (which is a palindrome).
• An O(n²) idea (for example, walking to the k-th node from the end for every k) would be 10⁵ × 10⁵ = 10¹⁰ steps → TLE. Roughly 10⁸ simple steps is the limit.
• Values are 0 to 9: small, nothing special.
• The teacher's usual reminder: in linked-list questions O(n²) is rare. Aim for linear time, and then try to bring the space down to O(1).

3Intuition: solve it on an array first

Forget the list. On an array [1, 2, 3, 2, 1] we'd use two pointers: left at the start, right at the end. Compare the two values. If they match, move left forward and right backward, and compare again. If any pair doesn't match, it can't be a palindrome, so stop at once.

[1, 2, 3, 2, 1]
 L           R    1 = 1 ✓ → move both
    L     R       2 = 2 ✓ → move both
       LR         left == right → stop → True

4Building the logic: when do the pointers stop?

The teacher looks at both lengths:

• Odd (5 values): after two moves left and right land on the same index (the middle). A value always equals itself, so stop.
• Even (4 values, [1, 2, 2, 1]): L=0,R=3 → L=1,R=2 → next move gives L=2,R=1. They never meet. Left crosses right, and every pair has been checked.

Both cases are covered by one rule: keep going while left < right.

But we have a linked list, not an array. The right pointer would have to step backwards, and the arrows don't allow that. So the brute force simply copies the values into an array first and then runs the same two-pointer check.

(In the video she calls the list "doubly linked" for a moment. That's a slip: it's a singly linked list, and that's exactly why we can't walk backwards.)

5Approach steps

1. Walk the list and append every value to vals.
2. Set i = 0, j = len(vals) - 1.
3. While i < j: if vals[i] != vals[j] return False; else i += 1, j -= 1.
4. If the loop finishes without a mismatch, return True.

6Code (Python)

class Solution:
    def isPalindrome(self, head):
        vals = []
        curr = head
        while curr:                    # copy the values out
            vals.append(curr.val)
            curr = curr.next

        i, j = 0, len(vals) - 1        # two pointers on the array
        while i < j:                   # stop when they meet (odd) or cross (even)
            if vals[i] != vals[j]:
                return False           # one mismatch is enough
            i += 1
            j -= 1
        return True

7Code line by line

8Dry run

With [1, 2, 3, 4, 1]: step 1 compares 1 vs 1 ✓, step 2 compares 2 vs 4 → False, and we never look at the middle.

9Complexity & remember

• Time O(n) + O(n/2) = O(3n/2): n steps to copy, then n/2 rounds of comparing, because both pointers move in the same round.
• Space O(n) for the array.

Part B · Optimal: middle → reverse second half → compare

1The question (same), with a new goal

Same input and output, but now with O(1) extra space: no array.

2What the constraints tell us

• At least 1 node → head is never None, so slow = fast = head is safe.
• Up to 10⁵ nodes → a few linear passes are fine. O(n²) is not.

3Intuition: make the right pointer able to walk backwards

The teacher goes through the patterns one by one to pick a tool:

• Basic operations (insert, delete, search) → we aren't changing the list's content, so no.
• Fast & slow → used to find the middle or detect a cycle. Not the main idea… but keep it in mind.
• Reversal → here's the key. The two-pointer idea failed only because the right pointer can't go backwards. But if the arrows of the second half pointed backwards, a walker starting at the last node could move towards the middle using plain .next. So we only need to reverse half the list.
• And how do we find where the half starts? That's exactly what fast & slow is for. So both patterns work together.

before:              [1] → [2] → [3] → [2] → [1] → None
second half reversed:[1] → [2] → [3] ← [2] ← [1]
                     head1                   head2
Now head1 walks right and head2 walks left, both with .next

4Building the logic step by step

Step 1: find the middle with fast & slow

Odd example 1 2 3 2 1:

start
[1] → [2] → [3] → [2] → [1] → None
slow/fast

move 1
[1] → [2] → [3] → [2] → [1] → None
      slow  fast

move 2
[1] → [2] → [3] → [2] → [1] → None
            slow        fast

stop: fast.next is None → middle = slow = [3] (position 2)

Even example 1 2 2 1:

start
[1] → [2] → [2] → [1] → None
slow/fast

move 1
[1] → [2] → [2] → [1] → None
      slow  fast

move 2
[1] → [2] → [2] → [1] → None
            slow        fast

stop: fast is None → middle = slow = [2] (position 2)

In both cases slow ends on the node where the second half starts (for odd length, the middle node itself).

Step 2: reverse from slow to the end

Keep head where it is: if we moved it, we'd lose the first half. Reverse the piece that starts at slow, using the four lines from the previous video. For the odd example, the piece is [3] → [2] → [1]:

start: prev = None, curr = slow
None   [3] → [2] → [1] → None
prev   curr

round 1: nxt = curr.next, curr.next = prev (red), then move
None ← [3]   [2] → [1] → None
prev   curr  nxt
       prev  curr   ← after moving

round 2: nxt = curr.next, curr.next = prev (red), then move
None ← [3] ← [2]   [1] → None
       prev  curr  nxt
             prev  curr   ← after moving

round 3: nxt = curr.next, curr.next = prev (red), then move
None ← [3] ← [2] ← [1]   None
             prev  curr  nxt
                   prev  curr   ← after moving

Now prev is on the last node, the head of the reversed half. The teacher calls it head2, and the original head head1. The whole picture:

[1] → [2] → [3] ← [2] ← [1]
head1        ↓          head2 (= prev)
            None
head1's walk: 1, 2, 3, then None     head2's walk: 1, 2, 3, then None

Step 3: compare, walking both pointers forward

• Loop while head2 is not None. Head2's piece is the shorter one (or equal), so it decides when we're done. It ends in None because of the reversal.
• If head1.val != head2.val → return False immediately.
• Else move both: head1 = head1.next, head2 = head2.next.
• If the loop ends without a mismatch → return True.

5Approach steps

1. slow = fast = head. While fast and fast.next: slow 1 step, fast 2 steps.
2. Reverse the list starting at slow with prev / curr / nxt. The new head is prev.
3. left = head, right = prev.
4. While right: if the values differ → False; else move both one step.
5. Return True.

6Code (Python)

class Solution:
    def isPalindrome(self, head):
        # 1. find the middle
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. reverse the second half (starting at slow)
        prev = None
        curr = slow
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        # 3. compare the first half with the reversed second half
        left, right = head, prev        # head1 and head2
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

7Code line by line

8Dry runs

Odd: 1 → 2 → 3 → 2 → 1

After steps 1 and 2 (drawn above): head1 = [1] (first), head2 = [1] (last).

Only 3 rounds for 5 nodes, which matches the teacher's count.

Even: 1 → 2 → 2 → 1

slow ends on the 3rd node (the second 2). Reversing [2] → [1] gives [1] → [2] → None:

[1] → [2] → [2] ← [1]
head1        ↓    head2
            None
head1's walk: 1, 2, 2   head2's walk: 1, 2

Here head1's piece is longer (it still reaches the second 2), and that's fine: we stop on head2.

Not a palindrome: 1 → 2 → 3 → 4 → 1

slow ends on [3]. Reversing [3] → [4] → [1] gives head2 = [1] → [4] → [3] → None. Round 1: 1 vs 1 ✓. Round 2: 2 vs 4 → return False.

9Complexity & remember

• Finding the middle: O(n/2), because fast moves 2 steps per round.
• Reversing the second half: O(n/2), the normal reversal is O(n) but here it only touches half the list.
• Comparing: O(n/2), both pointers move in the same round. For 5 nodes, only 3 rounds.
• Total O(3n/2) = O(n) time, O(1) space. We used a few pointers and no array.

The teacher says the brute force was "2n" when she compares at the end, but by her own counting earlier it's also n + n/2 = 3n/2. So the time is about the same. The real win is space: O(n) → O(1). On LeetCode the optimal version also ran faster, since it doesn't build an array.

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

s = Solution()
print(s.isPalindrome(build([1, 2, 3, 2, 1])))   # True
print(s.isPalindrome(build([1, 2, 2, 1])))      # True
print(s.isPalindrome(build([1, 2])))            # False
print(s.isPalindrome(build([7])))               # True
print(s.isPalindrome(build([1, 2, 3, 4, 1])))   # False

Based on this video: Palindrome Linked List | Reversal pattern