Unit 6 Session 2 (Click for link to problem statements)
TIP102 Unit 5 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
HAPPY CASE
Input: 1 -> 2 -> 2 -> 3 -> 3
Output: 1
Explanation: Duplicates of 2 and 3 are removed, leaving only 1.
EDGE CASE
Input: 1 -> 1 -> 1
Output: (Empty)
Explanation: All nodes are duplicates and are thus removed.
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.
This problem involves removing duplicates from a sorted linked list, which is typically tackled using a pointer to track the last unique node and another to skip duplicates.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a temp node to handle edge cases easily, and two pointers to manage duplicates.
1) Initialize a temp node with next pointing to head.
2) Use two pointers: one to keep track of the last node before a series of duplicates (prev) and another to traverse and skip duplicates (current).
3) Adjust links to skip over duplicates.
4) Return the modified list starting from temp's next.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def delete_dupes(head):
# Use a temp node to simplify head operations
temp = Node(0)
temp.next = head
# `prev` is the last node before the current sequence of duplicates or unique values
prev = temp
current = head
while current:
# Move current to skip over all duplicates
while current.next and current.value == current.next.value:
current = current.next
# If `prev.next` is `current`, no duplicates were found between `prev` and `current`
if prev.next == current:
prev = prev.next
else:
# Otherwise, skip all duplicates
prev.next = current.next
# Move current to the next distinct value
current = current.next
return temp.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.
O(N)
where N
is the number of nodes in the list. Each node is processed once.O(1)
since no extra space is used beyond a few pointers for management.