Applying Efficient Techniques to Linked List Challenges in TypeScript

Introduction to the Lesson

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.

LinkedList Implementation

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;
        }
    }
}

Problem 1: Linked List Deduplication

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.

Problem 1: Efficient Approach Explanation

Problem 1: Solution Building

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.

Sign up

Join the 1M+ learners on CodeSignal

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