Linked Lists and Interview Challenges with Kotlin

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

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.

A naive approach would be to browse each book and compare it with every other title in a nested loop fashion. As with any large library, this approach would be cumbersome, with a time complexity of $O(n^2)$. It also scales poorly with larger datasets because the time taken to process increases exponentially with each additional book—much like searching an entire library to check for duplicates each time a new book is added.

To address the issues of the naive approach, we use a more strategic method akin to maintaining a checklist: marking off each book we come across. This method, replicated in our algorithm, employs a mutableSetOf to record unique titles. Consequently, we reduce our time complexity to $O(n)$. Here's how we declare our HashSet in Kotlin: val seenBooks = mutableSetOf<Int>().

Let's delve into the step-by-step code:

fun removeDuplicates(head: ListNode?): ListNode? {
    // 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.
    val seenBooks = mutableSetOf<Int>()
    var 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 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
}

With this explanation, we've clarified the importance of each line of code in the context of the overall strategy for duplicate elimination. We implemented a systematic approach to traverse the list and used a mutableSetOf to avoid repetitively processing the same value while maintaining efficient traversal.