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. 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

2. 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

3. Consider the following Python code that removes the 2nd node from the end of the list 1 -> 2 -> 3 -> 4 -> 5. What is the printed output after execution?

easy

A. 1 2 4 5

B. 1 2 3 5

C. 1 3 4 5

D. 2 3 4 5

Solution

1. Step 1: Trace recursion from end

   Recursion returns indices from the end: node 5 returns 1, node 4 returns 2, node 3 returns 3, etc.

2. Step 2: Identify node to remove

   When idx == n+1 = 3, node 3's next pointer skips node 4, effectively removing node 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches list with 4 removed: 1 2 3 5 [OK]

Hint: Recursion index counts from end; remove node at idx = n+1 [OK]

Common Mistakes:

• Removing the node at idx == n instead of n+1
• Off-by-one errors in recursion index
• Confusing which node to skip

4. What is the time complexity of the fast and slow pointer algorithm for detecting a cycle in a linked list of length n?

medium

A. O(n) because the slow pointer traverses the list once and the fast pointer catches up quickly

B. O(n) because each node is visited at most twice by the pointers

C. O(n log n) due to repeated pointer comparisons

D. O(n^2) because the fast pointer moves twice as fast as the slow pointer

Solution

1. Step 1: Analyze pointer movements

   The slow pointer moves one step at a time, the fast pointer moves two steps. They meet within O(n) steps if a cycle exists.

2. Step 2: Confirm total steps taken

   Each node is visited at most twice by the pointers combined, so the total time complexity is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity confirmed by pointer meeting logic [OK]

Hint: Each node visited at most twice by pointers [OK]

Common Mistakes:

• Mistaking fast pointer speed as doubling complexity
• Assuming repeated comparisons cause log factor

5. What is the space complexity of the recursive reorderList implementation shown below, considering a linked list of length n?

medium

A. O(log n) -- recursion divides list in halves

B. O(1) -- only constant extra pointers used

C. O(n) -- recursion stack grows linearly with list length

D. O(n^2) -- nested recursive calls cause quadratic space

Solution

1. Step 1: Analyze recursion depth

   Each recursive call moves one node forward, so recursion depth is n.

2. Step 2: Determine space usage

   Each call adds a stack frame, so total auxiliary space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack grows linearly with input size [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming recursion is O(1) space
• Confusing recursion with divide-and-conquer
• Thinking nested calls multiply space