Singly linked list

Overview

A singly linked list is a chain of nodes where each node stores a value and a pointer to the next node. The list is identified by its head; the last node points to null. Unlike arrays, nodes are scattered in memory, so there is no index arithmetic: reaching the kth node means walking k steps.

The payoff is cheap structural change. Once you hold a reference to a node, inserting or removing the node after it is O(1), because you only rewire pointers. Almost every linked list interview problem is about rewiring pointers correctly without losing part of the list.

When to use it

• Frequent insertions and deletions at the front, or next to a node you already hold.
• You do not need random access by index.
• Implementing stacks, queues, adjacency lists, or hash map buckets.
• The problem gives you a ListNode head (most linked list interview questions).

Problem patterns it solves

Where it is used in real software

Key terms

Node

An object with val and next.

Head

Reference to the first node; null for an empty list.

Tail

The last node, whose next is null.

Dummy node

A placeholder before the head so edge cases at the head disappear.

Traversal

Following next pointers from head until null: O(n).

Reversing a list in place

1. 1
   Start with prev = null, curr = head

   prev will become the new head; curr is the node being processed.

2. 2
   Save next

   next = curr.next, because you are about to overwrite curr.next and would lose the rest of the list.

3. 3
   Reverse the pointer

   curr.next = prev.

4. 4
   Advance both

   prev = curr; curr = next.

5. 5
   Return prev

   When curr is null, prev is the old tail, now the new head.

Remove all nodes with value 6 using a dummy head

head = 6 -> 1 -> 6 -> 2, val = 6

The dummy node made removing the original head identical to removing any other node, so there is no special case.

Implementation

1class ListNode {2  constructor(val, next = null) {3    this.val = val;4    this.next = next;5  }6}7 8function reverseList(head) {9  let prev = null;10  let curr = head;11  while (curr) {12    const next = curr.next; // save the rest13    curr.next = prev;       // reverse the link14    prev = curr;15    curr = next;16  }17  return prev;18}19 20function removeElements(head, val) {21  const dummy = new ListNode(0, head);22  let prev = dummy;23  while (prev.next) {24    if (prev.next.val === val) prev.next = prev.next.next;25    else prev = prev.next;26  }27  return dummy.next;28}29 30function mergeTwoLists(a, b) {31  const dummy = new ListNode(0);32  let tail = dummy;33  while (a && b) {34    if (a.val <= b.val) { tail.next = a; a = a.next; }35    else { tail.next = b; b = b.next; }36    tail = tail.next;37  }38  tail.next = a ?? b;39  return dummy.next;40}41 42function addTwoNumbers(l1, l2) {43  const dummy = new ListNode(0);44  let tail = dummy, carry = 0;45  while (l1 || l2 || carry) {46    const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;47    carry = Math.floor(sum / 10);48    tail.next = new ListNode(sum % 10);49    tail = tail.next;50    l1 = l1?.next;51    l2 = l2?.next;52  }53  return dummy.next;54}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Losing the rest of the list.

  Fix: Save curr.next before overwriting it.

• Null pointer errors at the end.

  Fix: Check curr and curr.next before dereferencing; with fast pointers check fast && fast.next.

• Special-casing the head.

  Fix: Use a dummy node and return dummy.next.

• Returning the old head after reversing.

  Fix: Return prev, the new head.

Interview questions

Practice problems