Linked List – Tech Interview Dot Org

How does one find a loop in a singly linked list in O(n) time using constant memory? You cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.).

Solution

I first figured this out when I was asked the question in a Microsoft interview, so there’s verification that one question in the book was from a real interview. The best part of this problem is that I actually needed to write the code out for it a little while ago to detect a bug.

One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there’s a loop.

Now for another puzzle.. I think the next question I had to answer was something along the lines of “OK, How do you remove a loop in a linked list with the same constraints?” The latter question definitely seems harder, but in the sequence of questions I’d already answered for the interviewer, the solution was pretty obvious. I’ll leave that solution to someone else today.

Hm. I think I should pick up that book. I’ve always wondered where people got their juicy interview riddles.. I’ve always just repeated ones I’ve heard before or made up new ones along the same lines.

💡Strategies for Solving This Problem

Linked List Operations

This is a general linked list problem that usually asks you to implement common operations. Let me cover the most frequently asked ones.

Common Operations

1. Insertion: Beginning, end, at position

2. Deletion: By value, at position

3. Search: Find node by value

4. Reverse: Covered in other problems

5. Find middle: Slow/fast pointer

6. Detect cycle: Covered separately

The Dummy Node Trick

Use a dummy node at the start to simplify edge cases. Makes insertion/deletion code cleaner because you never need to update head pointer directly.

The Two-Pointer Patterns

Find middle: Slow moves 1 step, fast moves 2. When fast reaches end, slow is at middle.

Nth from end: Move fast n steps ahead, then move both until fast reaches end.

Cycle detection: If fast ever equals slow, there's a cycle.

What Interviewers Look For

Handling null/empty lists
Not losing references (causing memory leaks)
Edge cases: single node, two nodes
Clean code without lots of special cases

At Various Companies

Every company asks linked list questions. They're fundamental. The key is knowing the patterns (dummy node, two pointers, recursion) and applying them cleanly.

Most common: "Remove nth node from end" (fast/slow pointers), "Merge two sorted lists" (like merge sort), "Find intersection of two lists" (length difference trick).

✅Solution

Solution: Common Linked List Operations

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }

    // Insert at beginning - O(1)
    insertAtHead(val) {
        const newNode = new ListNode(val);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }

    // Insert at end - O(n)
    insertAtTail(val) {
        const newNode = new ListNode(val);

        if (this.head === null) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }

    // Insert at position - O(n)
    insertAt(val, index) {
        if (index < 0 || index > this.size) return false;

        if (index === 0) {
            this.insertAtHead(val);
            return true;
        }

        const newNode = new ListNode(val);
        let current = this.head;

        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }

        newNode.next = current.next;
        current.next = newNode;
        this.size++;
        return true;
    }

    // Delete by value - O(n)
    delete(val) {
        if (this.head === null) return false;

        // Delete head
        if (this.head.val === val) {
            this.head = this.head.next;
            this.size--;
            return true;
        }

        let current = this.head;
        while (current.next !== null) {
            if (current.next.val === val) {
                current.next = current.next.next;
                this.size--;
                return true;
            }
            current = current.next;
        }

        return false;  // Not found
    }

    // Delete at position - O(n)
    deleteAt(index) {
        if (index < 0 || index >= this.size) return false;

        if (index === 0) {
            this.head = this.head.next;
            this.size--;
            return true;
        }

        let current = this.head;
        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }

        current.next = current.next.next;
        this.size--;
        return true;
    }

    // Search - O(n)
    find(val) {
        let current = this.head;
        let index = 0;

        while (current !== null) {
            if (current.val === val) return index;
            current = current.next;
            index++;
        }

        return -1;  // Not found
    }

    // Find middle (fast/slow pointers) - O(n)
    findMiddle() {
        if (this.head === null) return null;

        let slow = this.head;
        let fast = this.head;

        while (fast !== null && fast.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // Find nth from end (two pointers) - O(n)
    findNthFromEnd(n) {
        if (n <= 0) return null;

        let fast = this.head;
        let slow = this.head;

        // Move fast n steps ahead
        for (let i = 0; i < n; i++) {
            if (fast === null) return null;  // n > length
            fast = fast.next;
        }

        // Move both until fast reaches end
        while (fast !== null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    // Print list
    print() {
        const arr = [];
        let current = this.head;
        while (current !== null) {
            arr.push(current.val);
            current = current.next;
        }
        console.log(arr.join(" -> "));
    }

    // Get length
    length() {
        return this.size;
    }
}

// Tests
const list = new LinkedList();

list.insertAtTail(1);
list.insertAtTail(2);
list.insertAtTail(3);
list.insertAtTail(4);
list.insertAtTail(5);

console.log("Original:");
list.print();  // 1 -> 2 -> 3 -> 4 -> 5

console.log("Middle:", list.findMiddle().val);  // 3

console.log("2nd from end:", list.findNthFromEnd(2).val);  // 4

list.insertAt(99, 2);
console.log("After insert at index 2:");
list.print();  // 1 -> 2 -> 99 -> 3 -> 4 -> 5

list.delete(99);
console.log("After delete 99:");
list.print();  // 1 -> 2 -> 3 -> 4 -> 5

console.log("Find 3:", list.find(3));  // 2 (index)

Useful Helper: Remove Nth From End

function removeNthFromEnd(head, n) {
    const dummy = new ListNode(0);
    dummy.next = head;

    let fast = dummy;
    let slow = dummy;

    // Move fast n+1 steps ahead
    for (let i = 0; i <= n; i++) {
        if (fast === null) return head;  // n too large
        fast = fast.next;
    }

    // Move both until fast reaches end
    while (fast !== null) {
        slow = slow.next;
        fast = fast.next;
    }

    // Remove node
    slow.next = slow.next.next;

    return dummy.next;
}

Useful Helper: Merge Two Sorted Lists

function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // Attach remaining
    current.next = l1 !== null ? l1 : l2;

    return dummy.next;
}

Complexity Summary

Operation	Time	Notes
Insert at head	O(1)	Always fast
Insert at tail	O(n)	Need to traverse (use tail pointer for O(1))
Insert at position	O(n)	Need to traverse
Delete	O(n)	Need to find node
Search	O(n)	Linear scan
Find middle	O(n)	Fast/slow pointers
Nth from end	O(n)	Two-pointer trick

Common Patterns

Dummy node: Simplifies head operations


const dummy = new ListNode(0);
dummy.next = head;
// ... do operations ...
return dummy.next;  // New head

Two pointers (fast/slow): Find middle, cycle detection


let slow = head, fast = head;
while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow is at middle

Two pointers (gap): Nth from end


let slow = head, fast = head;
for (let i = 0; i < n; i++) fast = fast.next;
while (fast) {
    slow = slow.next;
    fast = fast.next;
}
// slow is nth from end

Edge Cases

Empty list: head === null
Single node: head.next === null
Two nodes: Test fast/slow pointers
Invalid index/n: Return null or false