## 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?
• Can the input list be empty?
• Yes. The linked list can be empty.
``````HAPPY CASE
Output: true

Output: false

EDGE CASE
Output: true``````

## 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, we want to consider the following approaches:

• Multiple Pass. If we were able to take multiple passes of the linked list, would that help solve the problem?

• This may help us determine the length of the list. We can split linked list in half and reverse the second half. And check head and reversed nodes.
• Dummy Head. Would using a dummy head as a starting point help simplify our code and handle edge cases?

• There are no edge cases that a dummy head would help handle.
• Two Pointer. If we used two pointers to iterate through the list at different speeds, would that help us solve this problem?

• Two pointers could help us in this problem. It helps with middle of linked list and reversing it.

## 3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: (Approach 1: Recursion Advanced) Use the recusive stack to check last node against the first node and repeat.

``````1) Initialize a front pointer
2) Define Recursive Call: To check front pointer against entire stack of nodes(reversed nodes).
a) Recursive check on next node otherwise return false
b) Ensure front pointer is equal to stack node otherwise return false
c) Move front pointer.
At end of call stack return True
4) Return Recursive Call``````

General Idea: (Approach 2: Split/Reverse Linked List) Split the list in half and reverse half of it. Check the regular linked list and reverse linked list.

```1) Split list in half
2) Reverse second half of list
3) Check each node between regular linked list and reversed linked list
4) Return True if no differences were found```

⚠️ Common Mistakes

• Mutiple passes will slow down code and make code more complex.

## 4: I-mplement

Implement the code to solve the algorithm.

``````class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# Initialize a front pointer

# Define Recursive Call: To check front pointer against entire stack of nodes(reversed nodes).
def recursiveCheck(curr: Optional[ListNode]) -> bool:
if curr:
# Recursive check on next node otherwise return false
if not recursiveCheck(curr.next):
return False
# Ensure front pointer is equal to stack node otherwise return false
elif self.frontPointer.val != curr.val:
return False
# Move front pointer
else:
self.frontPointer = self.frontPointer.next
# At end of call stack return True
return True

# Return Recursive Call
``````

``````class Solution:
def isPalindrome(self, head: ListNode) -> bool:
return True

# Split list in half

while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None

# Reverse second half of list
rev = self.getReversed(l2)

# Check each node between regular linked list and reversed linked list
while l1 and rev:
if l1.val != rev.val:
return False
l1, rev = l1.next, rev.next

# Return True if no differences were found
return True

def getReversed(self, h):
if not h:
return h
curr, prev = h, None
while curr:
nextNode = curr.next
curr.next = prev
prev = curr
curr = nextNode
return prev``````

## 5: R-eview

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

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

## 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 we need to traverse all the nodes in the linked list.
• Space Complexity: `O(1)` because we only need several pointers for memory in the split/reverse linked list solution.
• Do note `O(N)` is required for the advanced recursion solution because we need to store the current node in the call stack. 