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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {ListNode}
def delete_duplicates(head)
    current = head

    while current && current.next
        if current.val == current.next.val
           current.next = current.next.next 
        else
            current = current.next
        end
    end

    head
end

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current = head

        while current and current.next:
            if current.val == current.next.val:
                # Skip the duplicate
                current.next = current.next.next
            else:
                # Move to the next node
                current = current.next

        return head

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.

1
2
3
4
5
6
7
8

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        cur=head
        while cur:
            while cur.next and cur.next.val==cur.val:
                cur.next=cur.next.next
            cur=cur.next
        return head

Problem Classification

  1. 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.

  2. 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.

  3. In-Place 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:

  1. 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.

  2. Variables and Data Types: The code involves object-oriented programming. There are object references (head, cur), and the objects are of a custom class type (ListNode).

  3. 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.

  4. 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.

  5. 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.

Problem-Solving Approach:

  1. 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.

  2. Define the problem requirements: Given a sorted linked list, delete all duplicates such that each element appears only once.

  3. 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.

  4. 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.

  5. 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

  1. Linked List:

We first need a simple linked list class for our drills.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Creating a linked list: 1 -> 2 -> 2 -> 3
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)
  1. Variables and Data Types:
1
2
3

# Object references and custom data types
node = head  # node is a reference to a ListNode object
print(node.val)  # Accessing object properties
  1. Loops (While Loop):
1
2
3
4
5

# Traversing a linked list using a while loop
node = head
while node is not None:
    print(node.val)
    node = node.next
  1. Conditional Statements (If):
1
2
3
4
5
6

# Check if the next node exists and if it has the same value as the current node
node = head
if node.next is not None and node.next.val == node.val:
    print("Next node is a duplicate")
else:
    print("Next node is not a duplicate")
  1. Pointer Manipulation:
1
2
3
4

# Skipping over a node in a linked list
node = head
if node.next is not None and node.next.val == node.val:
    node.next = node.next.next  # Skip over the next node

Problem Specific Drill:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def deleteDuplicates(head):
    node = head
    while node is not None:
        while node.next is not None and node.next.val == node.val:
            node.next = node.next.next  # Skip over the next node
        node = node.next
    return head

# Creating a linked list: 1 -> 2 -> 2 -> 3
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)

# Deleting duplicates
head = deleteDuplicates(head)

# Printing the list to verify duplicates are deleted
node = head
while node is not None:
    print(node.val)
    node = node.next

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.