Applying Efficient Techniques to Linked List Challenges in TypeScript

Today, we will tackle common interview challenges regarding linked lists, focusing on honing your problem-solving skills. We'll explore ways to streamline and refine our coding techniques when working with linked lists. By the end, you'll have a better grasp of crafting efficient algorithms and writing clean, effective TypeScript code.

In this lesson, we will use the same linked list implementation as in the previous lesson, but with one additional method to display the list:

class ListNode<T> {
    value: T;
    next: ListNode<T> | null;

    constructor(value: T) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList<T> {
    head: ListNode<T> | null;

    constructor() {
        this.head = null;
    }

    append(value: T): void {
        const newNode = new ListNode(value);

        if (this.head === null) {
            this.head = newNode;
            return;
        }

        let currentNode = this.head;
        while (currentNode.next !== null) {
            currentNode = currentNode.next;
        }

        currentNode.next = newNode;
    }

    show(): void {
        let currentNode = this.head;
        while (currentNode) {
            console.log(currentNode.value);
            currentNode = currentNode.next;
        }
    }
}

Our journey begins with a linked list with several duplicate values, resembling a situation where an email campaign wants to ensure duplicates don't get sent to the same recepient. We must eliminate duplicate nodes from our linked list.

We can use a set to keep track of the node values we've encountered. When a duplicate value surfaces, we bypass the node altogether, simplifying the process to a manageable single pass through the list or an $O(n)$ operation. This method efficiently preserves our list's uniqueness.

Here’s a step-by-step breakdown of how you'd implement such a solution:

function removeDuplicates<T>(list: LinkedList<T>): void {
    if (list.head === null || list.head.next === null) return;

    let currentNode = list.head;
    const seen = new Set<T>([currentNode.value]);

    while (currentNode.next !== null) {
        if (seen.has(currentNode.next.value)) {
            currentNode.next = currentNode.next.next;
        } else {
            seen.add(currentNode.next.value);
            currentNode = currentNode.next;
        }
    }
}

We begin with an empty set. Moving through the linked list, we add each unique value to the set. Whenever we encounter a value already in the set, we skip over the node containing it. This method ensures we only include each unique value once.