Linked list functions
Each pattern below is something you will reach for while solving linked-list problems. Skim the short description, then copy the snippets for common situations.
Prefer Overview for how linked lists work, and Problems for practice once problems are linked.
Node type & building
Define a node, then grow a list from values you already have.
ListNode
A value plus a pointer to the next node — the whole structure in one type.
// ——— classic singly-linked node ———
type ListNode = {
val: number;
next: ListNode | null;
};
function createNode(val: number, next: ListNode | null = null): ListNode {
return { val, next };
}
// ——— head of an empty list ———
let head: ListNode | null = null;fromArray()
Builds a list from an array — handy for tests and interview stubs.
function fromArray(values: number[]): ListNode | null {
const dummy: ListNode = { val: 0, next: null };
let tail = dummy;
for (const val of values) {
tail.next = { val, next: null };
tail = tail.next;
}
return dummy.next;
}
// ——— example ———
const head = fromArray([7, 3, 9, 1]);
// 7 → 3 → 9 → 1 → nulltoArray()
Walks the list into an array — useful for asserts and debugging.
function toArray(head: ListNode | null): number[] {
const out: number[] = [];
let cur = head;
while (cur) {
out.push(cur.val);
cur = cur.next;
}
return out;
}
toArray(fromArray([1, 2, 3])); // [1, 2, 3]Traverse & search
Start at the head and follow next until you find what you need — or null.
traverse()
Visits every node once from head to tail.
function traverse(head: ListNode | null, visit: (val: number) => void): void {
let cur = head;
while (cur) {
visit(cur.val);
cur = cur.next;
}
}
// ——— length ———
function length(head: ListNode | null): number {
let n = 0;
for (let cur = head; cur; cur = cur.next) n += 1;
return n;
}find()
Returns the first node whose value matches, or null.
function find(head: ListNode | null, target: number): ListNode | null {
let cur = head;
while (cur) {
if (cur.val === target) return cur;
cur = cur.next;
}
return null;
}
// ——— nth node (0-based hops from head) ———
function at(head: ListNode | null, index: number): ListNode | null {
let cur = head;
let i = 0;
while (cur && i < index) {
cur = cur.next;
i += 1;
}
return cur;
}Insert & delete
Rewire a couple of pointers. Head and tail are the special cases to practice.
insertHead()
Puts a new node at the front in O(1).
function insertHead(head: ListNode | null, val: number): ListNode {
return { val, next: head };
}
// ——— usage ———
let head: ListNode | null = null;
head = insertHead(head, 1);
head = insertHead(head, 2); // 2 → 1 → nullinsertTail()
Appends at the end — walk to the last node, then link.
function insertTail(head: ListNode | null, val: number): ListNode {
const node: ListNode = { val, next: null };
if (!head) return node;
let cur = head;
while (cur.next) cur = cur.next;
cur.next = node;
return head;
}
// ——— keep a tail pointer if you append often ———
// tail.next = node; tail = node;deleteHead()
Drops the first node by moving head forward.
function deleteHead(head: ListNode | null): ListNode | null {
return head ? head.next : null;
}
let head = fromArray([7, 3, 9]);
head = deleteHead(head); // 3 → 9 → nulldeleteValue()
Removes the first node with a given value. A dummy head keeps the real head simple.
function deleteValue(head: ListNode | null, target: number): ListNode | null {
const dummy: ListNode = { val: 0, next: head };
let prev = dummy;
while (prev.next) {
if (prev.next.val === target) {
prev.next = prev.next.next;
break;
}
prev = prev.next;
}
return dummy.next;
}
deleteValue(fromArray([7, 3, 9]), 3); // 7 → 9 → nullReverse
Flip every arrow. Iterative reverse is the version you want in an interview.
reverse()
Reverses the list in place with three pointers.
function reverse(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
reverse(fromArray([1, 2, 3])); // 3 → 2 → 1 → nullreverseBetween()
Reverses only the segment from left to right (1-based positions).
function reverseBetween(
head: ListNode | null,
left: number,
right: number,
): ListNode | null {
if (!head || left === right) return head;
const dummy: ListNode = { val: 0, next: head };
let before = dummy;
for (let i = 1; i < left; i++) before = before.next!;
const start = before.next!;
let prev = start;
let curr = start.next;
for (let i = left; i < right; i++) {
const next = curr!.next;
curr!.next = prev;
prev = curr!;
curr = next;
}
before.next = prev;
start.next = curr;
return dummy.next;
}Two pointers
Slow and fast (or a gap of k) unlock middle, nth-from-end, and cycle checks.
middleNode()
Slow walks one step, fast walks two — slow lands on the middle.
function middleNode(head: ListNode | null): ListNode | null {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
}
return slow;
}
// ——— even length: returns the second middle ———
middleNode(fromArray([1, 2, 3, 4, 5])); // node 3nthFromEnd()
Keep a gap of n between two pointers, then walk to the end.
function nthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy: ListNode = { val: 0, next: head };
let fast: ListNode | null = dummy;
let slow: ListNode | null = dummy;
for (let i = 0; i < n; i++) {
if (!fast) return null;
fast = fast.next;
}
while (fast?.next) {
fast = fast.next;
slow = slow!.next;
}
return slow!.next;
}hasCycle()
Floyd’s tortoise and hare — if they meet, there is a loop.
function hasCycle(head: ListNode | null): boolean {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
// ——— find cycle entry (when a cycle exists) ———
function detectCycle(head: ListNode | null): ListNode | null {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) {
let p = head;
while (p !== slow) {
p = p!.next;
slow = slow!.next;
}
return p;
}
}
return null;
}Doubly linked helpers
When you need to walk both ways, keep prev as well as next.
DoublyListNode
Same idea as a singly node, plus a pointer backward.
type DoublyListNode = {
val: number;
prev: DoublyListNode | null;
next: DoublyListNode | null;
};
function createDoubly(val: number): DoublyListNode {
return { val, prev: null, next: null };
}insertAfterDoubly()
Splices a node after a known node — update both directions.
function insertAfterDoubly(node: DoublyListNode, val: number): DoublyListNode {
const neu: DoublyListNode = { val, prev: node, next: node.next };
if (node.next) node.next.prev = neu;
node.next = neu;
return neu;
}
// ——— delete a known node (not head/tail edge cases) ———
function deleteDoubly(node: DoublyListNode): void {
if (node.prev) node.prev.next = node.next;
if (node.next) node.next.prev = node.prev;
}Merge & dummy head
A dummy node simplifies edge cases when building or merging lists.
mergeTwoLists()
Merges two sorted lists into one sorted list.
function mergeTwoLists(
a: ListNode | null,
b: ListNode | null,
): ListNode | null {
const dummy: ListNode = { val: 0, next: null };
let tail = dummy;
while (a && b) {
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a ?? b;
return dummy.next;
}dummy head pattern
Park a fake node in front so the real head is never a special case.
// ——— delete all nodes matching target ———
function deleteAll(head: ListNode | null, target: number): ListNode | null {
const dummy: ListNode = { val: 0, next: head };
let cur = dummy;
while (cur.next) {
if (cur.next.val === target) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}
// ——— build while scanning ———
const dummy: ListNode = { val: 0, next: null };
let tail = dummy;
// … append with tail.next = node; tail = node;
const result = dummy.next;