A linked list is a linear data structure where each element (node) contains data and a reference (pointer) to the next node. Unlike arrays, elements are not stored in contiguous memory.
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
// Create: 1 -> 2 -> 3
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Advantages: Dynamic size, efficient insertion/deletion at head. Disadvantages: No random access, extra memory for pointers.
Singly linked list: Each node has a next pointer only. Traversal is one direction.
Doubly linked list: Each node has both next and prev pointers, allowing bidirectional traversal.
// Singly Linked Node
class SinglyNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
// Doubly Linked Node
class DoublyNode {
constructor(val) {
this.val = val;
this.next = null;
this.prev = null;
}
}
Insert at head: Create a new node, point it to the current head, then update head.
Insert at tail: Traverse to the last node and set its next to the new node.
function insertAtHead(head, val) {
const newNode = new ListNode(val);
newNode.next = head;
return newNode; // new head
}
function insertAtTail(head, val) {
const newNode = new ListNode(val);
if (!head) return newNode;
let curr = head;
while (curr.next) curr = curr.next;
curr.next = newNode;
return head;
}
Insert at head: O(1) | Insert at tail: O(n) (O(1) if tail pointer is maintained).
To delete a node, adjust the previous node's next pointer to skip the target node.
function deleteNode(head, val) {
if (!head) return null;
if (head.val === val) return head.next;
let curr = head;
while (curr.next && curr.next.val !== val) {
curr = curr.next;
}
if (curr.next) {
curr.next = curr.next.next;
}
return head;
}
// List: 1->2->3->4, delete 3
// Result: 1->2->4
Time: O(n) | Space: O(1)
Use three pointers: prev, curr, and next. Iterate through the list, reversing each pointer.
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev; // new head
}
// 1->2->3->4 becomes 4->3->2->1
Time: O(n) | Space: O(1). This is one of the most common interview questions.
Floyd's Cycle Detection (Tortoise and Hare) uses two pointers: slow moves 1 step, fast moves 2 steps. If they meet, a cycle exists.
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;
}
Time: O(n) | Space: O(1). To find the cycle start, after detecting the cycle, reset one pointer to head and advance both by 1 step until they meet again.
Use the slow and fast pointer technique. When fast reaches the end, slow is at the middle.
function findMiddle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 1->2->3->4->5 => middle is 3
// 1->2->3->4 => middle is 3 (second of two middles)
Time: O(n) | Space: O(1)
Use a dummy node and compare values from both lists, appending the smaller node each time.
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let tail = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 || l2;
return dummy.next;
}
Time: O(n + m) | Space: O(1) — we reuse existing nodes.
Use the two-pointer gap technique: advance the fast pointer n steps ahead, then move both until fast reaches the end.
function removeNthFromEnd(head, n) {
const dummy = new ListNode(0);
dummy.next = head;
let fast = dummy, slow = dummy;
for (let i = 0; i <= n; i++) fast = fast.next;
while (fast) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
// 1->2->3->4->5, n=2 => 1->2->3->5
Time: O(n) in a single pass | Space: O(1)
Choose based on the access and mutation patterns:
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert at tail | O(1)* | O(n) / O(1)** |
| Delete at head | O(n) | O(1) |
* Amortized | ** With tail pointer
Use the slow and fast pointer technique. Slow moves one step, fast moves two steps. When fast reaches the end, slow is at the middle.
function findMiddle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // middle node
}
// Input: 1 -> 2 -> 3 -> 4 -> 5 => Output: node 3
// Input: 1 -> 2 -> 3 -> 4 => Output: node 3 (second middle)
Time: O(n) | Space: O(1)
Use Floyd's cycle detection. Phase 1: slow & fast pointers meet inside the cycle. Phase 2: reset one pointer to head — they meet at the cycle start.
function detectCycleStart(head) {
let slow = head, fast = head;
// Phase 1: detect cycle
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) break;
}
if (!fast || !fast.next) return null; // no cycle
// Phase 2: find start
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // cycle start node
}
// Input: 3 -> 2 -> 0 -> -4 (tail connects to node 2) => Output: node 2
// Input: 1 -> 2 (tail connects to node 1) => Output: node 1
Time: O(n) | Space: O(1)
Use a dummy head node and compare the current nodes of both lists, advancing the smaller one each time.
function mergeTwoLists(l1, l2) {
const dummy = { next: null };
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}
// Input: 1->2->4, 1->3->4 => Output: 1->1->2->3->4->4
// Input: [], 0 => Output: 0
Time: O(n + m) | Space: O(1)
Use two pointers. Advance the fast pointer n steps ahead, then move both until fast reaches the end. Slow is now at the nth-from-end node.
function removeNthFromEnd(head, n) {
const dummy = { next: head };
let fast = dummy, slow = dummy;
for (let i = 0; i <= n; i++) fast = fast.next;
while (fast) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // remove nth from end
return dummy.next;
}
// Input: 1->2->3->4->5, n=2 => Output: 1->2->3->5
// Input: 1, n=1 => Output: []
Time: O(n) | Space: O(1)
Find the middle (slow/fast pointers), reverse the second half, then compare both halves from outside in.
function isPalindrome(head) {
// 1. Find middle
let slow = head, fast = head;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
// 2. Reverse second half
let prev = null, curr = slow;
while (curr) { const tmp = curr.next; curr.next = prev; prev = curr; curr = tmp; }
// 3. Compare
let left = head, right = prev;
while (right) {
if (left.val !== right.val) return false;
left = left.next; right = right.next;
}
return true;
}
// Input: 1->2->2->1 => Output: true
// Input: 1->2 => Output: false
// Input: 1->2->3->2->1 => Output: true
Time: O(n) | Space: O(1)
Connect the tail to the head to form a circle. The new tail is at position (length - k % length - 1). Break the circle there.
function rotateRight(head, k) {
if (!head || !head.next || k === 0) return head;
let tail = head, len = 1;
while (tail.next) { tail = tail.next; len++; }
tail.next = head; // make circular
const steps = len - (k % len);
let newTail = head;
for (let i = 1; i < steps; i++) newTail = newTail.next;
const newHead = newTail.next;
newTail.next = null;
return newHead;
}
// Input: 1->2->3->4->5, k=2 => Output: 4->5->1->2->3
// Input: 0->1->2, k=4 => Output: 2->0->1
Time: O(n) | Space: O(1)
Digits are stored in reverse order. Traverse both lists simultaneously, sum digits plus carry, and build the result list.
function addTwoNumbers(l1, l2) {
const dummy = { next: null };
let curr = dummy, carry = 0;
while (l1 || l2 || carry) {
const sum = (l1?.val || 0) + (l2?.val || 0) + carry;
carry = Math.floor(sum / 10);
curr.next = { val: sum % 10, next: null };
curr = curr.next;
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;
}
return dummy.next;
}
// Input: (2->4->3) + (5->6->4) [342 + 465] => Output: 7->0->8 [807]
// Input: (0) + (0) => Output: 0
Time: O(max(n, m)) | Space: O(max(n, m) + 1) for result
Traverse the list; whenever curr.val === curr.next.val, skip the next node by rewiring pointers.
function deleteDuplicates(head) {
let curr = head;
while (curr && curr.next) {
if (curr.val === curr.next.val) {
curr.next = curr.next.next; // skip duplicate
} else {
curr = curr.next;
}
}
return head;
}
// Input: 1->1->2 => Output: 1->2
// Input: 1->1->2->3->3 => Output: 1->2->3
Time: O(n) | Space: O(1)
Use two pointers. When pointer A reaches the end of list A, redirect it to head of list B, and vice versa. They meet at the intersection (or both reach null if no intersection).
function getIntersectionNode(headA, headB) {
let a = headA, b = headB;
while (a !== b) {
a = a ? a.next : headB;
b = b ? b.next : headA;
}
return a; // intersection node or null
}
// List A: 4->1->8->4->5
// List B: 5->6->1->8->4->5 => Output: node with value 8
Time: O(n + m) | Space: O(1)
Use a stack. When a node has a child, push the next node onto the stack and continue down the child. When next is null, pop from the stack.
function flatten(head) {
if (!head) return head;
const stack = [];
let curr = head;
while (curr) {
if (curr.child) {
if (curr.next) stack.push(curr.next);
curr.next = curr.child;
curr.child.prev = curr;
curr.child = null;
}
if (!curr.next && stack.length) {
const next = stack.pop();
curr.next = next;
next.prev = curr;
}
curr = curr.next;
}
return head;
}
// Input: 1 - 2 - 3 - 4 (3 has child 7 - 8 - 9)
// Output: 1 - 2 - 3 - 7 - 8 - 9 - 4
Time: O(n) | Space: O(depth)
Merge sort is ideal for linked lists (unlike quicksort which needs random access). Split at the middle using slow/fast pointers, recursively sort halves, then merge.
function sortList(head) {
if (!head || !head.next) return head;
// Find middle and split
let slow = head, fast = head.next;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
const mid = slow.next;
slow.next = null; // split
// Recurse and merge
return merge(sortList(head), sortList(mid));
}
function merge(l1, l2) {
const dummy = {};
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}
// Input: 4->2->1->3 => Output: 1->2->3->4
// Input: -1->5->3->4->0 => Output: -1->0->3->4->5
Time: O(n log n) | Space: O(log n) recursion stack
Use a Map from original nodes to their clones. First pass: create all clones. Second pass: wire next and random pointers using the map.
function copyRandomList(head) {
if (!head) return null;
const map = new Map();
let curr = head;
// Pass 1: create all clone nodes
while (curr) { map.set(curr, { val: curr.val, next: null, random: null }); curr = curr.next; }
// Pass 2: wire pointers
curr = head;
while (curr) {
if (curr.next) map.get(curr).next = map.get(curr.next);
if (curr.random) map.get(curr).random = map.get(curr.random);
curr = curr.next;
}
return map.get(head);
}
// Input: [[7,null],[13,0],[11,4],[10,2],[1,0]]
// Output: deep copy with same structure
Time: O(n) | Space: O(n)
Iteratively swap every two adjacent nodes. Use a dummy head to handle edge cases. Rewire the three pointer connections per pair.
function swapPairs(head) {
const dummy = { next: head };
let prev = dummy;
while (prev.next && prev.next.next) {
const a = prev.next;
const b = prev.next.next;
prev.next = b;
a.next = b.next;
b.next = a;
prev = a; // a is now behind b in the new order
}
return dummy.next;
}
// Input: 1->2->3->4 => Output: 2->1->4->3
// Input: 1->2->3 => Output: 2->1->3
Time: O(n) | Space: O(1)
Three steps: (1) find the middle, (2) reverse the second half, (3) interleave both halves.
function reorderList(head) {
// 1. Find middle
let slow = head, fast = head;
while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }
// 2. Reverse second half
let prev = null, curr = slow.next;
slow.next = null;
while (curr) { const tmp = curr.next; curr.next = prev; prev = curr; curr = tmp; }
// 3. Merge
let l1 = head, l2 = prev;
while (l2) {
const tmp1 = l1.next, tmp2 = l2.next;
l1.next = l2; l2.next = tmp1;
l1 = tmp1; l2 = tmp2;
}
}
// Input: 1->2->3->4 => Output: 1->4->2->3
// Input: 1->2->3->4->5 => Output: 1->5->2->4->3
Time: O(n) | Space: O(1)