Removing Duplicate Markers - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 2 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Duplicate Removal, Temporary Head Technique

1: U-nderstand

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?
  • What does the problem ask for?
    • The problem asks to remove all duplicate nodes from a sorted linked list, keeping only the unique nodes.
  • What should be returned?
    • The function should return the head of the updated linked list with duplicates removed.
HAPPY CASE
Input: trailhead = Node(1, Node(2, Node(3, Node(3, Node(4)))))
Output: 1 -> 2 -> 4
Explanation: The node with value 3 appears twice, so it is removed.

EDGE CASE
Input: trailhead = Node(1, Node(1, Node(1)))
Output: (empty list)
Explanation: All nodes have the same value and are duplicates, so the list becomes empty.

2: M-atch

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 involving Duplicate Removal, we want to consider the following approaches:

  • Temporary Head Technique: Use a temporary head node to simplify edge cases, such as when the first node has duplicates.
  • Pointer Manipulation: Traverse the list and carefully adjust pointers to remove duplicates while maintaining the structure of the list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list, and whenever we encounter a sequence of nodes with the same value, we will remove all nodes with that value, ensuring only unique values remain.

1) Initialize a temporary head node pointing to the original head of the list.
2) Initialize two pointers: `prev` pointing to the temporary head and `current` pointing to the original head.
3) Traverse the list:
    a) If the current node has a duplicate (i.e., `current.value == current.next.value`), skip all nodes with the same value.
    b) Update `prev.next` to point to the node after the last duplicate.
    c) If the current node has no duplicate, move `prev` to point to `current`.
4) Continue until all nodes have been processed.
5) Return the node next to the temporary head (the new head of the list).

⚠️ Common Mistakes

  • Forgetting to handle cases where the first node or the entire list consists of duplicates.
  • Incorrectly managing pointers, leading to loss of nodes or incorrect list structure.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# Function to remove duplicates from a sorted linked list
def remove_duplicate_markers(trailhead):
    temp_head = Node(0)  # Temporary temp head node
    temp_head.next = trailhead
    
    prev = temp_head  # Pointer to the node before the current sequence
    current = trailhead
    
    while current:
        # Check if current node has a duplicate
        if current.next and current.value == current.next.value:
            # Skip all nodes with the same value
            while current.next and current.value == current.next.value:
                current = current.next
            # Link prev to the node after the last duplicate
            prev.next = current.next
        else:
            # Move prev pointer to the current node
            prev = prev.next
        
        current = current.next  # Move current pointer to the next node
    
    return temp_head.next

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Example: Use the provided trailhead linked list to verify that the function correctly removes duplicate nodes.

6: E-valuate

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.

  • Time Complexity: O(N) because each node is visited exactly once during the traversal.
  • Space Complexity: O(1) because the algorithm uses a constant amount of extra space for pointers.