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?
HAPPY CASE Input: head = [1,2,2,1] Output: true Input: head = [1,2] Output: false EDGE CASE Input: head =  Output: true
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?
Dummy Head. Would using a dummy head as a starting point help simplify our code and handle edge cases?
Two Pointer. If we used two pointers to iterate through the list at different speeds, would that help us solve this problem?
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
Implement the code to solve the algorithm.
Approach #1: Recursion Advanced
class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: # Initialize a front pointer self.frontPointer = head # 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 return recursiveCheck(head)
Approach #2: Split/Reverse Linked List
class Solution: def isPalindrome(self, head: ListNode) -> bool: if not head or not head.next: return True # Split list in half # See [Middle of the Linked List](https://github.com/codepath/compsci_guides/wiki/Middle-of-the-Linked-List) prev, slow, fast = None, head, head while fast and fast.next: prev = slow slow = slow.next fast = fast.next.next prev.next = None l1, l2 = head, slow # 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 # See [Reversed Linked List](https://github.com/codepath/compsci_guides/wiki/Reverse-Linked-List) 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
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
N represents the number of nodes in the linked list.
O(N)because we need to traverse all the nodes in the linked list.
O(1)because we only need several pointers for memory in the split/reverse linked list solution.
O(N)is required for the advanced recursion solution because we need to store the current node in the call stack.