Mirror, Mirror - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 1 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Linked Lists, Palindrome Check, Slow and Fast Pointer Technique

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What does the problem ask for?
  • The problem asks to determine if the linked list reads the same forwards and backwards, i.e., if it is a palindrome.
• What approach can be used?
  • Use the slow and fast pointer technique to find the middle of the list, reverse the second half, and then compare the two halves.

HAPPY CASE
Input: list1 = Node("Phoenix", Node("Dragon", Node("Phoenix")))
Output: True
Explanation: The linked list reads the same forwards and backwards.

HAPPY CASE
Input: list2 = Node("Werewolf", Node("Vampire", Node("Griffin")))
Output: False
Explanation: The linked list does not read the same forwards and backwards.

EDGE CASE
Input: head = None
Output: True
Explanation: An empty list is considered a palindrome.

EDGE CASE
Input: head = Node("Phoenix")
Output: True
Explanation: A single-node list is considered a palindrome.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List problems involving Palindrome Check, we want to consider the following approaches:

• Two Pointers (Slow and Fast Pointer Technique): Use two pointers to find the middle of the list and then compare the two halves.
• Reversal: Reverse the second half of the list to compare it with the first half.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will find the middle of the linked list using slow and fast pointers. Then, reverse the second half of the list and compare it with the first half to check if it’s a palindrome.

1) If the list is empty or has only one node, return True (as it is a palindrome).
2) Use slow and fast pointers to find the middle of the list.
3) Reverse the second half of the list.
4) Compare the values of the first half with the reversed second half:
    a) If all values match, the list is a palindrome.
    b) If any value does not match, return False.
5) Restore the list (optional) by reversing the second half again.
6) Return True if the list is a palindrome, otherwise return False.

⚠️ Common Mistakes

• Forgetting to handle the case where the list is empty or has only one node.
• Incorrectly comparing the two halves, leading to false results.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# Function to reverse the linked list
def reverse(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

# Function to check if the linked list is a palindrome
def is_mirrored(head):
    if not head or not head.next:
        return True

    # Step 1: Find the middle using slow and fast pointers
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse the second half of the list
    second_half_start = reverse(slow)

    # Step 3: Compare the first half and the reversed second half
    first_half_start = head
    second_half_copy = second_half_start  # Keep a copy to restore the list later (if needed)
    while second_half_start:
        if first_half_start.value != second_half_start.value:
            return False
        first_half_start = first_half_start.next
        second_half_start = second_half_start.next

    # Step 4: Restore the second half (optional)
    reverse(second_half_copy)

    return True

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Example: Use the provided list1 and list2 linked lists to verify that the function correctly identifies whether the list is a palindrome.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the linked list.

• Time Complexity: O(N) because each node is visited at most twice.
• Space Complexity: O(1) because the algorithm uses a constant amount of extra space for pointers.