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?
N
) time and O(1) space solution.
N` being the number of items in the array.HAPPY CASE
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Input: head = [5,4,3,2,1], left = 1, right = 5
Output: [1,2,3,4,5]
EDGE CASE
Input: head = []
Output: []
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:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will initialize a previous node,current node, and a next node. We will then point the current node .next to the previous node and move the previous node to current node and current node to next node and repeat the process.
1) Initialize a previous node, a current node.
2) While current node is not null
a) Initialize a next node to temporarily hold the next node
b) Point current node .next to previous node
c) Set prev node to current node
d) Set current node to next node
3) Return previous node
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Initialize a previous node, a current node.
prev, curr = None, head
# While current node is not null
while curr:
# Initialize a next node to temporarily hold the next node
next = curr.next
# Point current node .next to previous node
curr.next = prev
# Set prev node to current node
prev = curr
# Set current node to next node
curr = next
# Return previous node
return prev
class Solution {
public ListNode reverseList(ListNode head) {
// Initialize a previous node, a current node.
ListNode prev = null;
ListNode curr = head;
// While current node is not null
while (curr != null) {
// Initialize a next node to temporarily hold the next node
ListNode next = curr.next;
// Point current node .next to previous node
curr.next = prev;
// Set prev node to current node
prev = curr;
// Set current node to next node
curr = next;
}
// Return previous node
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.
Assume N
represents the number of nodes in the linked list.
O(N)
because we may need to traverse all the nodes in the linked list.O(1)
because we only need three pointers for memory.