Deciphering Linked List Puzzles: Removing Duplicates and Calculating Intervals in Java

Introduction to Linked Lists and Interview Challenges

Welcome back! As we continue to master the art of interview-oriented problems using linked lists in Java, we're setting our sights on practical, algorithmic challenges you will likely face.

Problem 1: Eliminating Duplicates in Linked Lists

Consider the following real-life problem: You’re tasked with organizing a digital library where some books have been accidentally duplicated. You aim to identify and remove these redundant entries to ensure each title is unique in your catalog.

Problem 1: Naive Approach and Its Drawbacks

O(n^2)

Problem 1: Efficient Approach Explanation and Comparison

O(n)

Problem 1: Step-by-Step Solution with Detailed Explanation

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Java

public ListNode removeDuplicates(ListNode head) {
    // If the library is empty or has only one book, no duplicates can exist.
    if (head == null || head.next == null) {
        return head;
    }
    
    // We initiate our checklist to keep track of unique books we've already checked out.
    HashSet<Integer> seenBooks = new HashSet<>();
    ListNode current = head; // Start checking from the first book on the shelf.
    seenBooks.add(current.value); // The first book is always unique.

    while (current.next != null) {
        if (seenBooks.contains(current.next.value)) {
            // We've already seen this book, so we remove it from the shelf by 
            // redirecting the current pointer to the next unique book.
            current.next = current.next.next;
        } else {
            // Upon detecting a unique book, we add it to the checklist and move to the next on the shelf.
            seenBooks.add(current.next.value);
            current = current.next;
        }
    }
    
    // The cleaned-up library with no duplicate titles.
    return head;
}

Java

public double averageOfEveryThird(ListNode head) {
    // A race with fewer than three checkpoints doesn't provide enough data for averaging.
    if (head == null || head.next == null || head.next.next == null) {
        return 0.0;
    }
    
    // Here, we'll record the total times at selected checkpoints.
    int sum = 0; 
    // The number of checkpoints that have contributed to our sum.
    int count = 0; 
    ListNode current = head; // The start of the race.

    // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
    for (int index = 1; current != null; current = current.next, index++) {
        // Our timer activates at every third checkpoint.
        if (index % 3 == 0) {
            sum += current.value; // Add the checkpoint time to our total.
            count++; // Another checkpoint contributes to the average.
        }
    }
    
    // The average timing at every third checkpoint, calculated just as a timing system might do.
    return (double) sum / count;
}

public double averageOfEveryThird(ListNode head) {
    // A race with fewer than three checkpoints doesn't provide enough data for averaging.
    if (head == null || head.next == null || head.next.next == null) {
        return 0.0;
    }
    
    // Here, we'll record the total times at selected checkpoints.
    int sum = 0; 
    // The number of checkpoints that have contributed to our sum.
    int count = 0; 
    ListNode current = head; // The start of the race.

    // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
    for (int index = 1; current != null; current = current.next, index++) {
        // Our timer activates at every third checkpoint.
        if (index % 3 == 0) {
            sum += current.value; // Add the checkpoint time to our total.
            count++; // Another checkpoint contributes to the average.
        }
    }
    
    // The average timing at every third checkpoint, calculated just as a timing system might do.
    return (double) sum / count;
}

Java

public double averageOfEveryThird(ListNode head) {
    // A race with fewer than three checkpoints doesn't provide enough data for averaging.
    if (head == null || head.next == null || head.next.next == null) {
        return 0.0;
    }
    
    // Here, we'll record the total times at selected checkpoints.
    int sum = 0; 
    // The number of checkpoints that have contributed to our sum.
    int count = 0; 
    ListNode current = head; // The start of the race.

    // We use 'index' as our countdown timer, ticking off each checkpoint as we pass.
    for (int index = 1; current != null; current = current.next, index++) {
        // Our timer activates at every third checkpoint.
        if (index % 3 == 0) {
            sum += current.value; // Add the checkpoint time to our total.
            count++; // Another checkpoint contributes to the average.
        }
    }
    
    // The average timing at every third checkpoint, calculated just as a timing system might do.
    return (double) sum / count;
}

Introduction to Linked Lists and Interview Challenges

Problem 1: Eliminating Duplicates in Linked Lists

Problem 1: Naive Approach and Its Drawbacks

Problem 1: Efficient Approach Explanation and Comparison

Problem 1: Step-by-Step Solution with Detailed Explanation

Join the 1M+ learners on CodeSignal

Problem 2: Finding the Average of Every Third Element

Problem 2: Problem Actualization

Problem 2: Efficient Approach

Building the Solution Step-by-Step with Detailed Explanation

Lesson Summary