Lesson 9 · Linear structures

Singly Linked Lists

A singly linked list is a sequence of dynamically allocated nodes where each node points to the next. Because you can only move forward, mastering algorithms like cycle detection and finding the middle requires specific pointer tricks.

The One-Way Constraint and What It Costs

A singly linked list node holds a value and exactly one pointer, next. That single restriction — no way back — determines the cost of nearly every operation on the structure, so it is worth tracing the consequences deliberately rather than memorising a table.

Consequence one: no indexing. Reaching element k means starting at head and following next k times, an O(n) walk. There is no list[k], and any algorithm written as a loop over indices will be O(n²) on a linked list even when it is O(n) on an array.

Consequence two: deletion is not O(1). To remove node X you must rewrite the next pointer of the node before it, and the only route to that predecessor is a walk from the head comparing current.next == X. Holding a reference to X itself does not help. This is the specific weakness a doubly linked list is built to fix.

Consequence three: the tail is far away. Appending means walking the whole list unless a tail reference is maintained alongside head. Keeping one costs eight bytes and turns append into O(1), which is what lets a singly linked list serve as a queue.

There is a well-known trick worth knowing and worth qualifying: given a node that is not the last, you can fake its deletion in O(1) by copying the next node's value into it and unlinking that next node instead. It does not delete the node you were given, it deletes its successor after stealing the data — and it fails on the tail, where there is no successor to steal from.

No random access — element k costs an O(n) walk
Deleting a held node is O(n): the predecessor must be found
A tail reference makes append O(1)
Copy-the-successor 'O(1) delete' cannot work on the last node

Traversal, Insertion, and Deletion

Traversal is the loop everything else is built on: set current = head, and while current is not null, do the work and advance with current = current.next. Advancing before using the node, or forgetting to advance at all, produces the two most common infinite-loop and off-by-one bugs.

Inserting at the head is the structure's cheapest operation: newNode.next = head, then head = newNode. Two writes, no walk, and it works unchanged on an empty list because head being null simply makes the new node the only node.

Inserting after a known node p follows the same shape: newNode.next = p.next, then p.next = newNode. The order is not a stylistic choice. Writing p.next first discards the only reference to the rest of the list, and everything past p is silently orphaned.

Deleting the node after p is the mirror image: save victim = p.next, set p.next = victim.next, then release victim — free() in C, delete in C++, automatic elsewhere. Note that this deletes through the predecessor, which is the whole difficulty described above.

The general rule behind all of these is one line: save the pointer you are about to overwrite, before you overwrite it. When a rewiring feels uncertain, draw the nodes and number the writes.

Traverse with current = current.next until null
Head insertion is two writes and needs no empty-list branch
Set the new node's next before redirecting the old pointer
Deletion happens through the predecessor, not the victim

Reversal in Place

Reversing a singly linked list is the most-asked operation on the structure. Nothing moves in memory — only the next pointers are flipped to face the other way, and the node that was last becomes the head.

It takes exactly three pointers. prev starts at null, current starts at head, and nextTemp holds the untouched remainder. The loop body is four statements whose order is fixed: nextTemp = current.next, current.next = prev, prev = current, current = nextTemp.

Statement one is the one that cannot be skipped. The moment current.next is overwritten with prev, the only reference to the unprocessed suffix is gone. Saving it first is the entire technique.

The invariant to state in an exam answer: prev heads a fully reversed prefix, current heads an untouched suffix, and each iteration moves exactly one node across the boundary. When current reaches null the suffix is empty, so prev is the new head — return prev, not head.

The cost is O(n) time and O(1) space. The empty list and the single-node list both fall through correctly with no special handling, which is a useful thing to verify aloud rather than assume.

One iteration of the reversal loop — the order is mandatory
#	Statement	Why
1	`nextTemp = current.next`	Save the suffix before the link is destroyed
2	`current.next = prev`	Flip this node to face backwards
3	`prev = current`	Grow the reversed prefix
4	`current = nextTemp`	Step into the saved suffix

Three pointers: prev, current, nextTemp
Save next first — step 1 is not optional
Return prev; it is the new head
O(n) time, O(1) space, no edge-case branches

Key reference

Terms, operations, and practical uses

Node structure

NodeAn object containing a piece of data and a single pointer/reference to the next node in the sequence.
Head PointerThe only required reference to manage the list, pointing to the very first node.
Null ReferenceThe value stored in the final node's 'next' pointer, indicating the end of the list.

Algorithmic techniques

Runner TechniqueUsing two pointers that traverse the list at different speeds (e.g., slow moves 1 step, fast moves 2 steps).
Floyd's Cycle DetectionUsing the runner technique to detect infinite loops. If the fast pointer laps and equals the slow pointer, a cycle exists.
Dummy NodeA fake head node used to simplify edge cases when inserting or deleting the very first real node.

Operations

TraversalThe O(N) process of starting at the head and following pointers until null is reached.
In-Place ReversalFlipping all 'next' pointers to face backward using three tracking variables (prev, current, next_temp).
PredecessorThe node immediately before a target node. You must have a reference to the predecessor to delete a node in a singly linked list.

Implementation

Finding the Middle of a Linked List

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

head = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6))))))

slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# even length: fast lands on None, so slow stops on the SECOND middle
print(f'Middle node is {slow.val} (second middle of an even-length list)')

#include <iostream>
using namespace std;
struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {
    }
};
int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    head->next->next->next->next->next = new Node(6);
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // even length: fast lands on NULL, so slow stops on the SECOND middle
    cout << "Middle node is " << slow->val << " (second middle of an even-length list)\n";
}

class Main {
    static class Node {
        int val;
        Node next;
        Node(int x) {
            val = x;
        }
    }
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // even length: fast lands on null, so slow stops on the SECOND middle
        System.out.println("Middle node is " + slow.val + " (second middle of an even-length list)");
    }
}

Watch it run

Step through it

Running on List: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Output

Read all 8 Steps

Both pointers start at the head slow and fast both begin at node 1. Nothing is known about the list length — that is the point, we never count it.
slow +1, fast +2 One round: slow steps to node 2, fast steps to node 3. Every round the gap between them grows by exactly one node.
slow +1, fast +2 slow is at node 3, fast at node 5. slow has covered half the ground fast has, which is the whole invariant.
fast reaches the last node fast is at node 6, slow at node 4. fast.next is null, so fast cannot take another double step — the loop condition fails here.
slow holds the middle With 6 nodes there are two middles, 3 and 4. This loop stops on the second one, node 4. Stopping on the first instead is a one-line change to the loop condition, and interview questions do specify which.
Why it works fast travels exactly twice as far as slow. When fast has covered the full list, slow has covered half of it. No length counting, no second pass — one traversal, O(n) time and O(1) space.
Odd-length lists With 5 nodes, fast lands on the last node and slow lands on node 3 — the single true middle. The same loop handles both parities without a special case.
The same trick detects a cycle If the list loops back on itself, fast never reaches null. Instead it laps slow from behind and the two land on the same node. Equal pointers mean a cycle; a null fast means a clean end. One pattern, two classic problems.

The Runner Technique

Two references advancing through the same list at different speeds extract positional facts in a single pass with no extra memory — no counting pass, no auxiliary array, no hash set. slow takes one step per iteration, fast takes two.

Finding the middle: run until fast is null or fast.next is null. Since fast covers twice the ground, slow lands on the midpoint. Which of the two middle nodes you get on an even-length list depends on which null test comes first — worth stating explicitly rather than leaving to chance, since merge sort's split depends on it.

Detecting a cycle (Floyd's tortoise and hare): the same loop, but comparing the two references each iteration. If fast reaches null the list terminates and there is no cycle. If a cycle exists, fast must enter it, and thereafter closes the gap on slow by exactly one node per iteration — so they are guaranteed to meet, not merely likely to. That closing-by-one argument is the part an exam answer needs; without it the algorithm looks like a coincidence.

Finding where the cycle starts: after they meet, reset one reference to head and advance both one step at a time. Their next meeting is the entry node, because the distance from the head to the entry equals the distance from the meeting point to the entry measured around the loop.

The nth node from the end uses the same two-reference idea with a fixed gap instead of a speed difference: advance one reference n steps, then move both together until the leader hits null. The trailer is sitting on the answer, found in one pass rather than two.

slow moves 1, fast moves 2 — one pass, O(1) space
Meeting proves a cycle; reaching null disproves it
The gap shrinks by exactly one per step, so meeting is guaranteed
Fixed-gap variant finds the nth node from the end