Linked Lists

A linked list stores elements in separate nodes, where each node points to the next one. Unlike an array, the nodes aren’t next to each other in memory.

head
 |
 v
[1] -> [2] -> [3] -> [4] -> null

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(nullptr) {}
};

A doubly linked list also stores prev, so it can be walked in both directions, and a node can be removed without knowing the node before it.

Operation	Array	Linked list
Access the `i`-th element	`O(1)`	`O(n)`
Insert / delete at a known node	`O(n)`, shifts elements	`O(1)`
Insert / delete at the front	`O(n)`	`O(1)`
Cache friendliness	good	poor, nodes are spread out

In practice, arrays are usually faster. Linked lists are mostly used when you need O(1) removal and insertion at nodes you already hold, like in an LRU cache, and they’re very common in interviews.

Building a List

There is no container to construct, you allocate nodes and link them. Doing it by hand works for a couple of nodes but breaks down in a loop, since the first node has no head to hang off yet:

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);

Instead start with a dummy node and a tail pointer that always points at the last node so far. The dummy exists only so the first append has something to attach to, so every iteration is the same two lines and the real head is dummy.next:

ListNode* build(vector<int>& nums) {
  ListNode dummy(0);
  ListNode* tail = &dummy;
  for (int x : nums) {
    tail->next = new ListNode(x);
    tail = tail->next;
  }
  return dummy.next;
}

This is how you build the answer in problems like merging two sorted lists or adding two numbers, where the output is a new list rather than a rewiring of the input.

Appending at the front instead builds the list backwards, and needs no dummy since nullptr is a fine thing for the first node to point at. It’s the same loop as reversal:

ListNode* head = nullptr;
for (int x : nums) {
  ListNode* node = new ListNode(x);
  node->next = head;
  head = node;
}

Leetcode builds the list for you and never asks you to free it, so new without delete passes there. In your own code it leaks, so walk the list and delete as you go, saving next first. Inside a solution prefer rewiring the existing nodes over allocating new ones unless the input has to survive: rewiring is O(1) space, building a fresh list is O(n).

Reversal

Walk the list and point each node back at the previous one:

ListNode* reverse(ListNode* head) {
  ListNode* prev = nullptr;
  ListNode* curr = head;
  while(curr) {
    ListNode* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

Fast and Slow Pointers

Move slow one step and fast two steps at a time.

Middle: when fast reaches the end, slow is at the middle.

ListNode* middle(ListNode* head) {
  ListNode* slow = head;
  ListNode* fast = head;
  while(fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow; // for an even length, this is the second of the two middles
}

Where the cycle starts: after they meet, move one pointer back to head, then move both one step at a time. They meet again at the start of the cycle.

ListNode* cycleStart(ListNode* head) {
  ListNode* slow = head;
  ListNode* fast = head;
  while(fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if(slow == fast) {
      slow = head;
      while(slow != fast) {
        slow = slow->next;
        fast = fast->next;
      }
      return slow;
    }
  }
  return nullptr;
}

Complexity

Technique	Time	Extra space
Reverse / middle / cycle / `n`-th from end	`O(n)`	`O(1)`
Merge two sorted lists	`O(n + m)`	`O(1)`
Merge `k` sorted lists	`O(n log k)`	`O(k)`
Sort a list (merge sort)	`O(n log n)`	`O(log n)` recursive, `O(1)` bottom-up
LRU cache `get` / `put`	`O(1)`	`O(capacity)`

DSA: Linked Lists

Linked Lists

Building a List

Reversal

Fast and Slow Pointers

Complexity

Leetcode Practice

Basics

Fast and Slow Pointers

Reversal, Merging and Sorting

Design