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,3,3,4,4,5]
Output: [1,2,5]
Input: head = [1,2,2,2,5]
Output: [1,5]
EDGE CASE
Input: head = [1,1,1,2,3]
Output: [2,3]
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 Lists problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a previous node as a placeholder to demarcate where nodes have no longer duplicates and use it to point to the next node that has no duplicate. Repeat until end of linked list.
1) Create a dummy head. This will be our reference to our return list.
2) Create a prev pointer to point to next node that has not duplicates
3) Create curr pointer to check if curr node has no duplicate
4) Traverse the lists while prev and curr is not None
a) Check curr to see if it has duplicates
i) If curr has duplicates, point prev.next at next unique node and bypass curr node.
ii) Else curr has no duplicates set prev pointer at curr
5) Return dummy.next
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Create a dummy head. This will be our reference to our return list.
dummy = ListNode(val=0, next=head)
# Create a prev pointer to point to next node that has not duplicates
prev = dummy
# Create curr pointer to check if curr node has no duplicate
curr = prev.next
# Traverse the lists while prev and curr is not None
while prev and curr:
# Check curr to see if it has duplicates
next = curr.next
# If curr has duplicates, point prev.next at next unique node and bypass curr node.
if next and curr.val == next.val:
while next and curr.val == next.val:
next = next.next
prev.next = next
curr = next
# Else curr has no duplicates set prev pointer at curr
else:
prev = curr
curr = next
# Return dummy.next
return dummy.next
class Solution {
public ListNode deleteDuplicates(ListNode head) {
// Create a dummy head. This will be our reference to our return list.
// Create a prev pointer to point to next node that has not duplicates
// Create curr pointer to check if curr node has no duplicate
ListNode dummy = new ListNode(0), curr = head, prev = dummy;
prev.next = curr;
// Traverse the lists while prev and curr is not None
while(prev != null && curr != null) {
// Check curr to see if it has duplicates
ListNode next = curr.next;
// If curr has duplicates, point prev.next at next unique node and bypass curr node.
if (next != null && curr.val == next.val) {
while (next != null && curr.val == next.val) {
next = next.next;
}
prev.next = next;
curr = next;
}
// Else curr has no duplicates set prev pointer at curr
else {
prev = curr;
curr = next;
}
}
// Return dummy.next
return dummy.next;
}
}
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 need to traverse all numbers in linked listO(1)
because we only needed a dummy node, prev node, curr node, and next node.