Palindrome Linked List

▶

Steps

setup

Initialize pointers slow and fast at head

Both slow and fast pointers start at the head node (value 1). This sets up for finding the middle of the list.

💡 Starting both pointers at head allows fast to move twice as fast as slow, so slow will land at the middle.

Line:

slow = fast = head

💡 Both pointers begin at the start, ready to traverse the list at different speeds.

traverse

Move slow one step, fast two steps

Slow pointer moves to node 2 (value 2), fast pointer moves to node 3 (value 2). This advances pointers to find the middle.

💡 Fast moves twice as fast, so slow moves slower and will reach middle when fast reaches end.

Line:

slow = slow.next
fast = fast.next.next

💡 Slow is now at second node, fast is two nodes ahead, maintaining the speed ratio.

traverse

Move slow one step, fast two steps again

Slow moves to node 3 (value 2), fast tries to move two steps but reaches null (end of list).

💡 Fast reaching end signals slow is at middle; traversal to find middle is complete.

Line:

slow = slow.next
fast = fast.next.next

💡 Slow pointer now points to the start of the second half of the list.

reverse_link

Start reversing second half from slow

Begin reversing the list starting at slow (node 3). Initialize prev to null and current to slow.

💡 Reversing second half allows comparison from end towards middle.

Line:

prev = None
current = slow

💡 Setup for in-place reversal of second half.

reverse_link

Reverse link of current node (3)

Store next node (4), reverse current's next to prev (null), move prev to current (3), current to next (4).

💡 Reversing links one by one flips the second half in place.

Line:

nxt = current.next
current.next = prev
prev = current
current = nxt

💡 Node 3 now points backward to null, starting reversed list.

reverse_link

Reverse link of current node (4)

Store next node (null), reverse current's next to prev (3), move prev to current (4), current to next (null).

💡 Continuing reversal until current is null completes second half reversal.

Line:

nxt = current.next
current.next = prev
prev = current
current = nxt

💡 Node 4 now points to node 3, completing reversed second half.

compare

Set pointers for comparison

Set first_half_start to head (node 1) and second_half_start to prev (node 4, reversed half start).

💡 We will compare nodes from start and reversed second half to check palindrome.

Line:

first_half_start = head
second_half_start = prev

💡 Pointers now ready to compare corresponding nodes from both halves.

compare

Compare first nodes of both halves

Compare values: first_half_start.val (1) == second_half_start.val (1), they match. Move both pointers forward.

💡 Matching values mean palindrome check continues.

Line:

if first_half_start.val != second_half_start.val:
    result = False
    break
first_half_start = first_half_start.next
second_half_start = second_half_start.next

💡 First pair matches, so palindrome check proceeds.

compare

Compare second nodes of both halves

Compare values: first_half_start.val (2) == second_half_start.val (2), they match. Move both pointers forward.

💡 Matching second pair confirms palindrome for all nodes compared.

Line:

if first_half_start.val != second_half_start.val:
    result = False
    break
first_half_start = first_half_start.next
second_half_start = second_half_start.next

💡 All compared nodes match, palindrome confirmed.

reverse_link

Restore the second half by reversing again

Reverse the second half again starting from prev (node 4) to restore original list structure.

💡 Restoring list is optional but good practice to keep input unchanged.

Line:

reverse(second_half_copy)

💡 Reversing again returns second half to original order.

reconstruct

Return the result true

All comparisons matched, so the function returns true indicating the list is a palindrome.

💡 Final step confirms the palindrome check result.

Line:

return result

💡 The list is confirmed palindrome by the algorithm.

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

def reverse(head):
    prev = None  # STEP 4
    current = head  # STEP 4
    while current:  # STEP 5,6 loop
        nxt = current.next  # STEP 5
        current.next = prev  # STEP 5
        prev = current  # STEP 5
        current = nxt  # STEP 5
    return prev

def isPalindrome(head):
    if not head or not head.next:
        return True
    slow = fast = head  # STEP 1
    while fast and fast.next:  # STEP 2,3 loop
        slow = slow.next  # STEP 2,3
        fast = fast.next.next  # STEP 2,3
    second_half_start = reverse(slow)  # STEP 4-6
    first_half_start = head  # STEP 7
    second_half_copy = second_half_start
    result = True
    while second_half_start:  # STEP 8,9 loop
        if first_half_start.val != second_half_start.val:
            result = False
            break
        first_half_start = first_half_start.next
        second_half_start = second_half_start.next
    reverse(second_half_copy)  # STEP 10
    return result  # STEP 11

# Example usage:
if __name__ == '__main__':
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

📊

Palindrome Linked List - Watch the Algorithm Execute, Step by Step

Watching each pointer move and list modification helps you understand the algorithm's logic and why it works without guessing.

advance

1

→

2

→

2

→

1

advance

1

→

2

→

2

→

1

advance

1

→

2

→

2

→

1

reverse_link

1

→

2

→

2

→

1

reverse_link

1

→

2

→

2

→

1

reverse_link

1

→

2

→

2

→

1

compare

1

→

2

→

2

→

1

compare

1

→

2

→

2

→

1

Result: true

compare

1

→

2

→

2

→

1

Result: true

reverse_link

1

→

2

→

2

→

1

Result: true

reconstruct

1

→

2

→

2

→

1

Result: true

Key Takeaways

✓ Using fast and slow pointers efficiently finds the middle of the list in one pass.

This is hard to see from code alone because the pointer movements are subtle and happen simultaneously.

✓ Reversing the second half in place allows palindrome comparison without extra space.

Visualizing the reversal step-by-step clarifies how links are flipped and why this is safe.

✓ Comparing nodes from the start and reversed second half confirms palindrome property node-by-node.

Seeing each comparison and pointer advance helps understand how mismatches would be detected early.

Practice

1. Given the following code snippet for detecting a circular array loop, what is the return value when the input is nums = [2, -1, 1, 2, 2]?

easy

A. True

B. False

C. Raises an IndexError

D. Infinite loop

Solution

1. Step 1: Trace first iteration starting at index 0

   nums[0]=2 (positive), direction is forward. slow and fast start at 0.

2. Step 2: Move slow and fast pointers

   slow moves to index (0+2)%5=2, fast moves two steps: first to 2, then to (2+1)%5=3. Both nums[2] and nums[3] are positive, direction consistent.

3. Step 3: Next iteration

   slow moves to (2+1)%5=3, fast moves two steps: from 3 to (3+2)%5=0, then from 0 to (0+2)%5=2. slow=3, fast=2, not equal yet.

4. Step 4: Next iteration

   slow moves to (3+2)%5=0, fast moves two steps: from 2 to (2+1)%5=3, then from 3 to (3+2)%5=0. slow=0, fast=0, pointers meet.

5. Step 5: Check cycle length

   Check if slow == next_index(slow): next_index(0) = 2, not equal, so cycle length > 1.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Cycle detected with consistent direction and length > 1 [OK]

Hint: Pointers meet at index 0 with valid cycle -> returns True [OK]

Common Mistakes:

• Confusing slow and fast pointer positions
• Ignoring direction check
• Mistaking single-element loop as valid

2. You are given a circular array where each element represents the number of steps to move forward or backward. The goal is to determine if there exists a cycle where all moves are in the same direction and the cycle length is greater than 1. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Fast and slow pointer technique (Floyd's cycle detection) adapted for circular arrays with direction checks

B. Greedy approach that tries to jump as far as possible each time without revisiting indices

C. Dynamic programming to store reachable indices and cycle lengths

D. Brute force simulation with a visited set for each start index

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify algorithm that efficiently detects cycles

   Fast and slow pointer (Floyd's cycle detection) can detect cycles in O(n) time and O(1) space, with added direction checks to ensure cycle validity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Fast-slow pointer is classic for cycle detection in sequences [OK]

Hint: Cycle detection in sequences -> fast-slow pointer [OK]

Common Mistakes:

• Thinking greedy jumps detect cycles correctly
• Assuming DP applies here
• Using brute force is optimal

3. You are given a singly linked list and an integer n. The task is to remove the n-th node from the end of the list in a single pass without using extra space for storing nodes. Which approach guarantees this optimal solution?

easy

A. Traverse the list twice: first to count nodes, second to remove the target node.

B. Sort the list first, then remove the node at position length - n.

C. Use two pointers with a fixed gap of n+1 nodes, moving together until the fast pointer reaches the end.

D. Use a dynamic programming approach to store intermediate results for each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing the n-th node from the end in one pass without extra storage.

2. Step 2: Identify the two-pointer technique for single-pass removal

   Using two pointers with a gap of n+1 nodes ensures the slow pointer stops just before the target node, allowing removal in one pass.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is classic for single-pass linked list problems [OK]

Hint: Two pointers with gap n+1 enable single-pass removal [OK]

Common Mistakes:

• Using two passes instead of one
• Trying to sort the list which is unnecessary
• Confusing DP with linked list traversal

4. Examine the following code snippet intended to detect the start of a cycle in a linked list. Identify the line containing the subtle bug that can cause a runtime error or infinite loop.

medium

A. Line 5: fast = fast.next.next

B. Line 3: while fast:

C. Line 7: if slow == fast:

D. Line 11: while ptr1 != ptr2:

Solution

1. Step 1: Check loop condition safety

   The loop condition only checks if fast is not None, but fast.next may be None, so fast.next.next can cause an exception.

2. Step 2: Identify fix

   The loop condition should check both fast and fast.next to avoid null pointer exceptions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Accessing fast.next.next without checking fast.next causes runtime error [OK]

Hint: Always check fast and fast.next before accessing fast.next.next [OK]

Common Mistakes:

• Missing fast.next check
• Returning meeting point as cycle start
• Infinite loop due to wrong loop condition

5. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow