iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Linked Lists

By · Reviewed & last updated · Part of Data Structures & Algorithms

A linked list is a chain of nodes, each holding a value and a pointer to the next. O(1) insert/remove at the head; O(n) random access. Doubly-linked variants add a prev pointer.

Reverse + classic two-pointer tricks

EXAMPLE
class Node {
    constructor(v, next = null) { this.v = v; this.next = next; }
}

// Reverse a list in O(n) / O(1)
function reverse(head) {
    let prev = null, cur = head;
    while (cur) {
        [cur.next, prev, cur] = [prev, cur, cur.next];
    }
    return prev;
}

// Detect a cycle — Floyd's tortoise & hare
function hasCycle(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

// Find the middle (slow when fast reaches end)
function middle(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

// Merge two sorted lists
function merge(a, b) {
    const dummy = new Node(0);
    let tail = dummy;
    while (a && b) {
        if (a.v <= b.v) { tail.next = a; a = a.next; }
        else            { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a || b;
    return dummy.next;
}

Why it matters

Linked lists are popular interview questions but rare in practice — cache locality favours arrays in 95% of real workloads. Learn the patterns; reach for Array or Map in production.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
class Node { constructor(v, next = null) { this.v = v; this.next = next; } }

function reverseList(head) {
    let prev = null, cur = head;
    while (cur) [cur.next, prev, cur] = [prev, cur, cur.next];
    return prev;
}
Try it Yourself »

Discussion

Loading…