Remove Duplicates from Sorted List
Define the Terms Sorted: The value of the numbers in the nodes are in ascending order.
Define the Interface Input: head of the linked list Output: head of the linked list
Analyze the Input and Output
 We need to handle the edge case where we have 0 nodes
Identify the Invariants
Identify the constraints
 The number of nodes in the list is in the range [0, 300].
 100 <= Node.val <= 100
 The list is guaranteed to be sorted in ascending order.
Search the Problem Space
Classify the Problem
Analyze the Examples
Solve the Problem by Hand
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Do we need a sentinel node? No. Reason: We need to return the head of the linked list, we are not modifying the head node.
How many pointers do we need? One pointer
 Initialize the current pointer to head
 We need to compare the current node’s value with the next node’s value current.val == current.next.val If the values are the same, how do we delete the duplicate. current.next = current.next.next One pointer will work to delete multiple duplicate nodes in the list.
Two pointers Why
Floyd’s Algorithm (Fast/Slow pointers)
Analyze Time and Space Complexity
Time: O(N) Space: O(1)
Outline the Solution
 Pointer to traverse the linked list
 Compare with its next node
 Rewire the next link
 Return the head
Key Takeaways


Removing duplicates from a sorted linked list can be done by iterating through the list and comparing the current node’s value with the next node’s value. If the values are the same, we skip the duplicate by updating the next pointer of the current node.
Here’s a simple code snippet that demonstrates how to do this:


This code iterates through the list and skips the nodes with duplicate values by updating the next pointer. Since the list is guaranteed to be sorted, all duplicates of a value will be adjacent in the list, so this approach will remove all duplicates.
The time complexity of this code is (O(n)), where (n) is the number of nodes in the list, as we’re iterating through the list once. The space complexity is (O(1)) since we’re only using a constant amount of extra space.


Problem Classification
Linked List: The problem revolves around the manipulation of a linked list data structure. It involves traversing, accessing, and manipulating nodes in a linked list.
Data Cleaning: The problem is about removing duplicate data from a dataset (in this case, a linked list). Hence, it falls into the category of data cleaning or data preprocessing tasks.
InPlace Operations: The problem requires the modification of the linked list in place, i.e., no new linked list is created and the changes are made directly to the input linked list. This is common in problems that require optimization of space complexity.
The classification is somewhat subjective and can depend on how one chooses to view the problem. For example, one might argue this problem also belongs to a category like “Element Removal” or “Duplicates Handling”.
Language Agnostic Coding Drills
This code is a function to remove duplicates from a sorted linked list. Given a sorted linked list, the function deletes all duplicates such that each element appears only once.
Let’s break down the code into smaller units of learning:
Linked List: The concept of a linked list is key to this problem. Each element (node) in a linked list contains a value and a reference (link) to the next node in the sequence.
Variables and Data Types: The code involves objectoriented programming. There are object references (head, cur), and the objects are of a custom class type (ListNode).
Loops (While Loop): The code involves nested while loops. The outer loop is used to traverse the linked list. The inner loop is used to skip over duplicate elements.
Conditional Statements (If): The code uses conditional statements to check if the next node is not None and if the value of the next node is the same as the current node.
Pointer Manipulation: The main idea of the solution involves manipulating pointers in a linked list. If the next node has the same value as the current node, the next node is skipped by updating the next pointer of the current node to point to the next node of the next node.
ProblemSolving Approach:
Understand the problem: The problem is to delete duplicates from a sorted linked list. The sorted nature of the list ensures that all duplicates of a number are adjacent in the list.
Define the problem requirements: Given a sorted linked list, delete all duplicates such that each element appears only once.
Break down the problem: The problem can be broken down into subproblems:
 Traverse the linked list. For each node, if the next node has the same value, skip it by updating the next pointer.
Develop a solution: Pseudocode for the solution can be written as follows:
 Start with the head of the list. For each node in the list, if the next node is not None and has the same value, update the next pointer of the current node to skip the next node. Repeat this until the next node is None or has a different value. Move to the next node and repeat the process.
 Return the head of the list.
Test the solution: The solution should be tested with various inputs to ensure that it handles all scenarios. It’s especially important to test edge cases, such as an empty list, a list with only one node, and a list where all nodes have the same value.
Targeted Drills in Python
 Linked List:
We first need a simple linked list class for our drills.


 Variables and Data Types:


 Loops (While Loop):


 Conditional Statements (If):


 Pointer Manipulation:


Problem Specific Drill:
Now let’s combine all of these concepts into a drill specific to the problem at hand:


This drill exercises all the necessary concepts and builds up to the final solution. Each concept is demonstrated in isolation and then integrated into the final solution.