Linked Lists

intermediate5 problems· Prerequisites: Big O & Complexity, Arrays & Strings

Linked List Basics

A linked list consists of nodes, each containing a value and a pointer to the next node (and optionally the previous node).

Operation	Singly Linked	Doubly Linked
Access head	O(1)	O(1)
Access tail	O(n)	O(1)
Access by index	O(n)	O(n)
Insert at head	O(1)	O(1)
Insert at tail	O(n)	O(1)
Delete by value	O(n)	O(n)

When to use: Frequent insertions/deletions at the beginning, or when size is unknown. Otherwise, prefer arrays/lists.

Singly linked list nodeC#

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

// C# also has built-in LinkedList<T> (doubly linked)
var list = new LinkedList<string>();
list.AddFirst("c");
list.AddLast("d");
list.AddBefore(list.First, "b");

// But for interviews, you'll usually implement the node class

Reversing a Linked List

Reversal is the most common linked list operation. The key: track three nodes - prev, current, and next - and reverse the pointer direction at each step.

Iterative reversalC#

// Reverse a singly linked list - O(n), O(1) space
ListNode ReverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;

    while (curr != null) {
        ListNode next = curr.next;  // save next
        curr.next = prev;           // reverse pointer
        prev = curr;                // move prev forward
        curr = next;                // move curr forward
    }

    return prev; // new head
}

Fast & Slow Pointer

Two pointers traverse the list at different speeds. The slow pointer moves 1 step, the fast pointer moves 2 steps.

Applications:

Cycle detection - if fast meets slow, there's a cycle (Floyd's algorithm)
Find middle - when fast reaches the end, slow is at the middle
Find nth from end - move fast n steps ahead, then advance both

Cycle detection and find middleC#

// Detect cycle - O(n), O(1) space
bool HasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast?.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

// Find middle node - O(n), O(1) space
ListNode FindMiddle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast?.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

When to Use Linked Lists

Linked lists shine when:

You frequently insert or delete at the head (O(1) vs O(n) for array)
The total size is unknown and grows/shrinks unpredictably
You're already iterating through all elements (no random access needed)
You need a lock-free concurrent data structure (CAS on pointers)

Linked lists are NOT the right choice when:

You need random access by index (O(n) - use an array)
Memory overhead matters (each node has pointer overhead)
Cache locality is important (nodes are scattered in memory)
The list is small (array wins for simplicity)

Decision guide:

Signal	Best choice
"Access element at index k"	Array
"Insert at front repeatedly"	Linked list
"Traverse all elements"	Either
"Memory is tight"	Array (less overhead)
"No idea how big it will get"	Dynamic array or linked list

Singly vs Doubly: Use doubly only if you need O(1) tail access or backward traversal. Otherwise singly is simpler and uses less memory.

Common Mistakes / Gotchas

Losing reference to the head If you move your head pointer without saving it first, you lose the entire list. Always keep a separate reference to head, or use a dummy node.

Null dereference on .next Always check node?.next != null (or node != null && node.next != null) before accessing node.next.next. This is the most common linked list bug.

Forgetting the "save next" step in reversal In iterative reversal: you must save curr.next before overwriting it. Without ListNode next = curr.next, you lose the rest of the list.

Assuming built-in linked list has O(1) index access No - list[5] on a linked list is O(n). That's why array lists exist.

Cycle detection without correct initialization Floyd's algorithm: start BOTH slow and fast at head. Starting fast at head.next can miss cycles in edge cases.

Common Interview Patterns

Reverse - full reversal, reverse between positions, reverse in k-groups
Merge - merge two sorted lists, merge k sorted lists
Fast & slow - cycle detection, middle, palindrome check
Dummy head - create a dummy node before the real head to simplify edge cases (especially with deletions)
Two lists - intersection, addition (sum two numbers represented as lists)

Losing reference to the head If you move your head pointer without saving it first, you lose the entire list. Always keep a separate reference to head, or use a dummy node.

Null dereference on .next Always check node?.next != null (or node != null && node.next != null) before accessing node.next.next. This is the most common linked list bug.

Forgetting the "save next" step in reversal In iterative reversal: you must save curr.next before overwriting it. Without ListNode next = curr.next, you lose the rest of the list.

Assuming built-in linked list has O(1) index access No - list[5] on a linked list is O(n). That's why array lists exist.

Cycle detection without correct initialization Floyd's algorithm: start BOTH slow and fast at head. Starting fast at head.next can miss cycles in edge cases.