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.

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.

Here is an example of how we might use this function:

let list = new LinkedList<number>();
list.append(1);
list.append(1);
list.append(3);
list.append(3);
list.append(3);
list.append(5);
removeDuplicates(list)
list.show();  // 1 3 5

It successfully removes all the duplicates from the defined list.

For our next challenge, let's calculate the average of every third element in a linked list. Picture yourself in a fruit orchard, tasting every third apple to understand the overall harvest quality. While you would only sample some apples, this systematic approach lets you estimate the batch's quality reliably.

Much like our orchard sampling, sampling at consistent intervals can reduce noise in signal processing, helping us focus on signal trends. Consider financial analysts, who might average quarterly results to understand a company's performance trend.

Here's how to implement this sampling:

function averageOfEveryThird<T>(list: LinkedList<number>): number {
    if (list.head === null) return 0; 

    let sum: number = 0, count: number = 0, index: number = 0;
    let currentNode: ListNode<number> | null = list.head;

    while (currentNode !== null) {
        if ((index + 1) % 3 === 0) {
            sum += currentNode.value;
            count++;
        }
        currentNode = currentNode.next;
        index++;
    }

    return parseFloat((sum / count).toFixed(2));
}

Our implementation starts with checks for a "no apples" scenario. Strolling through our orchard, we sample every third apple and update our running total. Note that we use (index + 1) in the condition (index + 1) % 3 === 0 because we need every third apple, and indexing starts with 0. Finally, we average our notes to convey the orchard's overall apple quality. Rounding our average to two decimal places is akin to briefly summarizing our tastings.

Here is an example of how we might use this function:

let list = new LinkedList<number>();
list.append(2);
list.append(3);
list.append(7);  // to be counted
list.append(2);
list.append(1);
list.append(5);  // to be counted
console.log(averageOfEveryThird(list)); // 6

The answer is 6 because it is the average value between the third value 7 and the sixth value 5.

In this session, we've applied discernment and mathematics to solve two linked list problems you're likely to encounter in job interviews. Using clear real-world analogies, we've related practical programming approaches to everyday tasks, enabling easier comprehension. By focusing on writing efficient TypeScript code, we've unraveled the problems to clear and swift solutions. Now, it's time to apply what you've learned in practical scenarios.