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 sorted singly linked list and need to remove all duplicate nodes so that each element appears only once. Which approach guarantees an optimal in-place solution with linear time complexity and constant extra space?

easy

A. Use a hash set to track seen values and remove duplicates by reconstructing the list.

B. Use a nested loop to compare each node with all subsequent nodes and remove duplicates.

C. Iterate once through the list, comparing each node with its next node and removing duplicates in-place.

D. Sort the list first, then remove duplicates by scanning through it.

Solution

1. Step 1: Understand the problem constraints

   The list is already sorted, so duplicates appear consecutively, allowing a single pass to remove them efficiently.

2. Step 2: Identify the optimal approach

   Iterating once and comparing each node with its next node lets us remove duplicates in-place with O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with pointer manipulation matches optimal solution [OK]

Hint: Sorted list allows single pass duplicate removal [OK]

Common Mistakes:

• Thinking nested loops are needed despite sorted input

2. You are given a singly linked list and asked to swap every two adjacent nodes, returning the modified list. Which approach guarantees an optimal solution that swaps nodes in-place without extra data structures and handles all edge cases efficiently?

easy

A. Use a greedy approach that swaps values instead of nodes to minimize pointer changes.

B. Use a recursive approach that swaps pairs by adjusting pointers and recurses on the rest of the list.

C. Use dynamic programming to store intermediate swapped sublists for reuse.

D. Use a brute force approach that creates a new list and inserts nodes in swapped order.

Solution

1. Step 1: Understand the problem constraints

   The problem requires swapping nodes in pairs by changing pointers, not just values, and must be done in-place.

2. Step 2: Identify the approach that swaps nodes recursively

   The recursive approach swaps the first two nodes, then recursively swaps the rest, ensuring all pairs are swapped correctly without extra space for new lists.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive pointer swapping matches problem requirements [OK]

Hint: Recursive pointer swapping fits in-place pairwise node swaps [OK]

Common Mistakes:

• Thinking swapping values is sufficient
• Using DP unnecessarily
• Creating new lists wastes space

3. Consider the following buggy code snippet for adding two linked lists representing numbers in forward order. Which line contains the subtle bug that causes incorrect results when the sum produces a carry beyond the most significant digit?

medium

A. Line 2: Calculating length of l1

B. Line 7: Calling addListsHelper recursively

C. Line 4: Padding the shorter list

D. Line 9: Returning head without handling carry

Solution

1. Step 1: Identify carry handling after addition

   The code calls addListsHelper which returns carry, but the carry is ignored before returning the head.

2. Step 2: Understand impact of missing carry

   If carry is non-zero, the result should prepend a new node with carry value; missing this causes incorrect sum for cases like 999 + 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Carry ignored after addition leads to wrong output length [OK]

Hint: Always check carry after recursive addition [OK]

Common Mistakes:

• Ignoring carry after final addition
• Incorrect padding causing misalignment
• Modifying input lists unexpectedly

4. Suppose you want to merge two sorted linked lists where nodes can be reused multiple times (i.e., each node can appear multiple times in the merged list). Which modification to the in-place merge algorithm correctly handles this scenario?

hard

A. Create a new list and copy nodes from both lists, allowing duplicates by reusing values but not nodes.

B. Use a recursive merge that creates new nodes for each occurrence to avoid pointer conflicts.

C. Modify the algorithm to allow nodes to be linked multiple times by not advancing pointers after attaching nodes.

D. Use the same in-place merge but reset pointers to the start of lists after each merge step.

Solution

1. Step 1: Understand node reuse constraints

   Reusing nodes multiple times in a linked list is impossible without creating new nodes because each node can only have one next pointer.

2. Step 2: Identify correct approach

   To allow duplicates, the algorithm must create new nodes for each occurrence, which recursion can do naturally by creating new nodes on each call.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive merge with new nodes handles duplicates safely [OK]

Hint: Nodes cannot be reused multiple times without duplication [OK]

Common Mistakes:

• Trying to reuse nodes by resetting pointers causes cycles
• Assuming in-place merge can handle duplicates without new nodes
• Not realizing linked list nodes have single next pointer

5. Suppose you want to modify the bottom-up merge sort on a linked list to handle the case where the list nodes can be reused multiple times (i.e., duplicates allowed and nodes can appear multiple times). Which modification is necessary to maintain correctness and efficiency?

hard

A. Add a hash set to track visited nodes during merge to prevent infinite loops caused by reuse.

B. No modification needed; the existing algorithm handles duplicates and reuse naturally.

C. Modify the merge function to create new nodes instead of reusing existing nodes to avoid cycles.

D. Switch to recursive merge sort to better handle node reuse and duplicates.

Solution

1. Step 1: Understand node reuse implications

   If nodes can be reused multiple times, re-linking existing nodes in merge can create cycles or corrupt list structure.

2. Step 2: Modify merge to create new nodes

   Creating new nodes during merge avoids modifying shared nodes, preventing cycles and preserving correctness.

3. Step 3: Evaluate other options

   Tracking visited nodes adds overhead and complexity; recursion does not solve reuse issues; no modification risks infinite loops.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Creating new nodes ensures safe merges with reused nodes [OK]

Hint: Reusing nodes requires copying to avoid cycles [OK]

Common Mistakes:

• Assuming existing merge works with reused nodes
• Trying to detect cycles dynamically instead of preventing
• Switching to recursion without addressing reuse