Linked List Data Structure: Reversal, Middle and Cycles

An array keeps its elements side by side in one block of memory, so arr[i] is instant but a new first element shifts every other one along. A linked list makes the opposite trade: each element lives in its own small object, a node, holding the value and a pointer to the next node. The nodes sit anywhere; the pointers put them in order.

Inserting and deleting become cheap and reaching the i-th element slow, and interviews test whether you can rewire pointers safely: the dummy head, reversal, and fast and slow pointers.

Why not just use an array

Keep a history with the newest event first. Each insert at index 0 of an array moves every element one place right, so 100,000 inserts cost about 5 × 10⁹ moves, far over a one-second limit. A list needs two pointer writes, however long it is.

1. Both hold 3, 8, 1, 6, and 0 must go in front. The array has one spare slot at the end; the new list node has been allocated but nothing points to it yet.
2. The array cannot put 0 anywhere but index 0, and index 0 is taken, so every element moves one place right, starting from the back: 4 writes before the new value is even stored.
3. Now 0 goes into index 0: 5 writes for 4 elements. With n elements it is n + 1, so 100,000 inserts at the front cost about 5 × 10⁹ moves.
4. The list first points the new node at the current first node: fresh.next = head. Nothing else changes, and the old list is still intact behind it.
5. Then head = fresh, and the list reads 0 → 3 → 8 → 1 → 6 → null. 2 pointer writes, the same for 4 nodes or 4 million: inserting at the front of a list is O(1), where the array paid O(n).

The price: no index arithmetic, so reaching the 50,000th node means following 49,999 pointers. Use an array to read by position, and a list to insert and delete where you already hold a pointer.

How a linked list is stored

A node has two fields, val and next; the list is just a pointer to the first node, the head, and the last node's next is null, which is where a walk stops. A singly linked list, as in the figure, walks forwards only. A doubly linked list adds a prev pointer per node, so it can walk backwards and delete a node it holds. A circular list's last node points back to the first, like the players in Find the Winner of the Circular Game.

Nodes allocated one by one usually sit far apart, so a walk jumps to a fresh cache line almost every node. Both walks are O(n), but the list's is often several times slower — why real code reaches for an array first.

The operations and their cost

The O(1) entries hold once you have the node: inserting at position 5,000 still walks 5,000 nodes first. Two rules keep rewiring safe: link the new node to what follows first, and delete "the node after prev", since a node does not know who points at it.

1. The list is 1 → 2 → 4 → 5 → null, and a new node holding 3 must go after the node holding 2, which the pointer node points at. The new node exists, but nothing points to it yet.
2. First connect the new node to what follows: fresh.next = node.next, so 3 points at 4. Done the other way round, node.next = fresh would erase the only pointer to 4 → 5, and the rest of the list would be lost.
3. Then node.next = fresh: 2 now points at 3. Two pointer writes, and no other node was touched, so inserting after a node you hold is O(1) however long the list is.
4. Redrawn in order, the list is 1 → 2 → 3 → 4 → 5 → null. Nothing moved in memory: only the arrows changed, which is the whole point of a linked list.
5. To delete 4, the node before it must be pointed past it, and a node does not know who points at it. So you hold prev, the node before the one to delete.
6. prev.next = prev.next.next: one write, and 3 points straight at 5. The 4 node is no longer reachable from head; in C++ you delete it, and the other three languages free it once nothing refers to it.
7. The list is 1 → 2 → 3 → 5 → null. Insert took two writes and delete one; the catch is finding the place, since reaching the i-th node means following i pointers from head.

The dummy head

Deleting the first node changes head itself, and code that special-cases it is where most list bugs live. A dummy head is an extra node in front whose value is never read: every real node now has a predecessor, one deletion rule works everywhere, and the answer is dummy.next.

1. Remove every 7 from 7 → 7 → 3 → 7 → 5 → null. A dummy node D goes in front, so even the first real node has a node before it, and every deletion is the same move: unlink the node after prev.
2. prev.next holds 7, so it is unlinked: prev.next = prev.next.next. That was the list's first node, yet the code is the same as anywhere else, because prev is the dummy. prev does not move.
3. This is why prev did not move: the node that slid into prev.next had not been checked, and it holds 7 too. It is unlinked the same way.
4. prev.next holds 3, which stays, so prev moves on to it. The list is now 3 → 7 → 5 → null from the dummy's next.
5. prev.next holds 7, so it is unlinked: 3 now points straight at 5. Again prev stays where it is.
6. prev.next holds 5, which stays, so prev moves on to it. The list is now 3 → 5 → null from the dummy's next.
7. prev.next is null, so the loop ends and the answer is dummy.next: 3 → 5 → null. 3 nodes unlinked in one pass, with no if for the head: O(n) time, O(1) space.

Reversing a linked list

Reversal is the most asked list question: turn every arrow round without making new nodes. Pointing cur.next backwards destroys the only pointer to the rest, so it is saved first — hence three pointers.

1. Every arrow has to point the other way, without making new nodes. prev starts at null, because the first node will become the last; cur starts at the head. The reversed part is empty and the rest is the whole list.
2. Step 1: save next = 2 first, because the next line overwrites the only pointer to it. Then cur.next = prev turns 1's arrow round to null, and prev and cur each step one node on.
3. Step 2: save next = 3, turn 2's arrow round to 1, step on. Each step moves one node from the front of the rest to the front of the reversed part.
4. Step 3: save next = 4, turn 3's arrow round to 2, step on. Each step moves one node from the front of the rest to the front of the reversed part.
5. Step 4: save next = 5, turn 4's arrow round to 3, step on. Each step moves one node from the front of the rest to the front of the reversed part.
6. Step 5: next is null, the end of the list. 5's arrow turns round to 4, and after stepping on, cur is null: every node has been turned.
7. cur is null, so prev heads the whole list, reversed: 5 → 4 → 3 → 2 → 1 → null. Why it is correct: at every step the reversed part and the rest were two whole lists, and each step moved one node across. One pass, three pointers: O(n) time, O(1) space.

Why it is correct: at every step prev heads a correctly reversed list of everything visited and cur heads the untouched rest. Each step moves one node across, so when cur is null, prev heads the whole list reversed: O(n) time, O(1) space.

Finding the middle with fast and slow pointers

Counting nodes and then walking half way takes two passes. Fast and slow pointers take one: slow moves one node per step and fast two, so when fast runs out, slow is half way.

1. Both pointers start at the head. On every step slow moves one node and fast moves two, while fast and fast.next both exist; when fast cannot move on, it has covered the list and slow has covered half of it.
2. Step 1: slow is on 2 in both lists and fast on 3: fast has gone twice as far.
3. Step 2: on 5 nodes fast lands on the last node, so fast.next is null and the loop stops with slow on 3, the middle. On 6 nodes fast.next is 6, so that loop goes on.
4. Step 3: on 6 nodes fast steps off the end to null and the loop stops with slow on 4: an even list has two middles and this returns the second. Start fast at head.next to get the first one, 3.

Test fast != null before fast.next != null, or the test itself dereferences null. On an even-length list the loop returns the second middle; start fast at head.next for the first, as when splitting a list for merge sort.

The code

The program builds a list with a dummy head, finds its middle, reverses it, and finds the middle of a six-node list.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// Builds a list from an array; the dummy head means the first node needs no special case.
Node* build(const vector<int>& values) {
    Node dummy(0);
    Node* tail = &dummy;
    for (int v : values) {
        tail->next = new Node(v);
        tail = tail->next;
    }
    return dummy.next;
}

void printList(const string& label, Node* head) {
    cout << label;
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->val << (cur->next != nullptr ? " -> " : "");
    }
    cout << "\n";
}

// Reverses the list in place with three pointers and returns the new head.
Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;  // save the rest before the link is overwritten
        cur->next = prev;        // turn this node's arrow round
        prev = cur;
        cur = next;
    }
    return prev;
}

// Fast moves two steps for each step of slow, so slow is halfway when fast runs out.
Node* middleNode(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

void freeList(Node* head) {
    while (head != nullptr) {
        Node* next = head->next;
        delete head;
        head = next;
    }
}

int main() {
    Node* head = build({1, 2, 3, 4, 5});
    printList("List:     ", head);
    cout << "Middle:   " << middleNode(head)->val << "\n";
    head = reverseList(head);
    printList("Reversed: ", head);
    Node* even = build({1, 2, 3, 4, 5, 6});
    cout << "Middle of 6 nodes: " << middleNode(even)->val << "\n";
    freeList(head);
    freeList(even);
    return 0;
}

public class Main {
    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }

    // Builds a list from an array; the dummy head means the first node needs no special case.
    static Node build(int[] values) {
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int v : values) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static void printList(String label, Node head) {
        StringBuilder line = new StringBuilder(label);
        for (Node cur = head; cur != null; cur = cur.next) {
            line.append(cur.val).append(cur.next != null ? " -> " : "");
        }
        System.out.println(line);
    }

    // Reverses the list in place with three pointers and returns the new head.
    static Node reverseList(Node head) {
        Node prev = null;
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;  // save the rest before the link is overwritten
            cur.next = prev;       // turn this node's arrow round
            prev = cur;
            cur = next;
        }
        return prev;
    }

    // Fast moves two steps for each step of slow, so slow is halfway when fast runs out.
    static Node middleNode(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        Node head = build(new int[] {1, 2, 3, 4, 5});
        printList("List:     ", head);
        System.out.println("Middle:   " + middleNode(head).val);
        head = reverseList(head);
        printList("Reversed: ", head);
        Node even = build(new int[] {1, 2, 3, 4, 5, 6});
        System.out.println("Middle of 6 nodes: " + middleNode(even).val);
    }
}

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


def build(values):
    """Build a list from a Python list; the dummy head means the first node needs no special case."""
    dummy = Node(0)
    tail = dummy
    for v in values:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


def print_list(label, head):
    parts = []
    cur = head
    while cur is not None:
        parts.append(str(cur.val))
        cur = cur.next
    print(label + " -> ".join(parts))


def reverse_list(head):
    """Reverse the list in place with three pointers and return the new head."""
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next   # save the rest before the link is overwritten
        cur.next = prev  # turn this node's arrow round
        prev = cur
        cur = nxt
    return prev


def middle_node(head):
    """Fast moves two steps for each step of slow, so slow is halfway when fast runs out."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow


head = build([1, 2, 3, 4, 5])
print_list("List:     ", head)
print("Middle:   " + str(middle_node(head).val))
head = reverse_list(head)
print_list("Reversed: ", head)
even = build([1, 2, 3, 4, 5, 6])
print("Middle of 6 nodes: " + str(middle_node(even).val))

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

// Builds a list from an array; the dummy head means the first node needs no special case.
function build(values) {
  const dummy = new Node(0);
  let tail = dummy;
  for (const v of values) {
    tail.next = new Node(v);
    tail = tail.next;
  }
  return dummy.next;
}

function printList(label, head) {
  const parts = [];
  for (let cur = head; cur !== null; cur = cur.next) parts.push(cur.val);
  console.log(label + parts.join(" -> "));
}

// Reverses the list in place with three pointers and returns the new head.
function reverseList(head) {
  let prev = null;
  let cur = head;
  while (cur !== null) {
    const next = cur.next; // save the rest before the link is overwritten
    cur.next = prev; // turn this node's arrow round
    prev = cur;
    cur = next;
  }
  return prev;
}

// Fast moves two steps for each step of slow, so slow is halfway when fast runs out.
function middleNode(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

let head = build([1, 2, 3, 4, 5]);
printList("List:     ", head);
console.log("Middle:   " + middleNode(head).val);
head = reverseList(head);
printList("Reversed: ", head);
const even = build([1, 2, 3, 4, 5, 6]);
console.log("Middle of 6 nodes: " + middleNode(even).val);

List:     1 -> 2 -> 3 -> 4 -> 5
Middle:   3
Reversed: 5 -> 4 -> 3 -> 2 -> 1
Middle of 6 nodes: 4

Detecting a cycle with Floyd's algorithm

A list has a cycle when some node points back to an earlier one, so a walk never ends. A hash set of visited nodes finds it with O(n) memory; Floyd's cycle detection needs only slow and fast. If fast reaches null there is no cycle; otherwise they meet, and a second phase finds where the loop starts.

1. Node 6 links back to node 3, so a walk never reaches null. Phase 1: slow moves one node a step and fast two. If the list ended, fast would reach null; here it goes round the loop.
2. Step 1: slow is on 2, still in the tail; fast is already on 3, inside the loop.
3. Step 2: slow is on 3, fast on 5. Going round, fast is 2 nodes behind slow, and each step closes that gap by one: slow gains one node, fast two.
4. Step 3: slow is on 4, fast on 3. Going round, fast is 1 node behind slow, and each step closes that gap by one: slow gains one node, fast two.
5. Step 4: they meet at 5. Inside the loop the gap from fast round to slow shrank by exactly one each step, and a whole number that drops by one cannot jump over zero. So they must meet, within one lap of slow entering the loop.
6. Phase 2 finds where the loop starts. slow made k = 4 moves and fast 8; the extra 4 were whole laps, so k is a multiple of L = 4. Put a back at the head and b at the meeting point, and move both one node at a time.
7. a moves to 2, b to 6. Both are 1 step from the loop's first node.
8. After μ = 2 steps both are on 3, the first node of the loop. a walked the tail; b walked μ steps on from a point k − μ past the entrance, k steps in all, which is whole laps, so it is back at the entrance too.

They must meet because, once both are in the loop, the gap from fast round to slow shrinks by exactly one per step, and a whole number falling by one cannot skip zero. With speeds 1 and 3 the gap would fall by two and could jump over it.

Phase two works by arithmetic: if the tail has μ nodes and slow made k moves, fast made 2k, and the extra k were whole laps. The meeting point is k − μ steps past the entrance, so μ more steps make k — whole laps — and reach the entrance, just as a pointer walking μ steps from the head does. Compare nodes, never values.

The code

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// Phase 1: slow moves one step, fast two. Returns where they meet, or nullptr if the list ends.
Node* meetingPoint(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return slow;  // the same node, not just the same value
    }
    return nullptr;
}

// Phase 2: one pointer from the head, one from the meeting point, one step each.
Node* cycleStart(Node* head) {
    Node* meet = meetingPoint(head);
    if (meet == nullptr) return nullptr;
    Node* a = head;
    Node* b = meet;
    while (a != b) {  // both are mu steps from the loop's first node
        a = a->next;
        b = b->next;
    }
    return a;
}

int main() {
    vector<Node*> nodes;
    for (int v = 1; v <= 6; v++) nodes.push_back(new Node(v));
    for (int i = 0; i + 1 < (int)nodes.size(); i++) nodes[i]->next = nodes[i + 1];
    Node* head = nodes[0];

    cout << "Straight list: " << (cycleStart(head) == nullptr ? "no cycle" : "cycle") << "\n";

    nodes.back()->next = nodes[2];  // 6 now points back to 3
    cout << "Tail linked back to 3: pointers meet at " << meetingPoint(head)->val
         << ", cycle starts at " << cycleStart(head)->val << "\n";

    for (Node* n : nodes) delete n;  // the vector, not the looped list, lists each node once
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }

    // Phase 1: slow moves one step, fast two. Returns where they meet, or null if the list ends.
    static Node meetingPoint(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return slow;  // the same node, not just the same value
        }
        return null;
    }

    // Phase 2: one pointer from the head, one from the meeting point, one step each.
    static Node cycleStart(Node head) {
        Node meet = meetingPoint(head);
        if (meet == null) return null;
        Node a = head;
        Node b = meet;
        while (a != b) {  // both are mu steps from the loop's first node
            a = a.next;
            b = b.next;
        }
        return a;
    }

    public static void main(String[] args) {
        List<Node> nodes = new ArrayList<>();
        for (int v = 1; v <= 6; v++) nodes.add(new Node(v));
        for (int i = 0; i + 1 < nodes.size(); i++) nodes.get(i).next = nodes.get(i + 1);
        Node head = nodes.get(0);

        System.out.println("Straight list: " + (cycleStart(head) == null ? "no cycle" : "cycle"));

        nodes.get(5).next = nodes.get(2);  // 6 now points back to 3
        System.out.println("Tail linked back to 3: pointers meet at " + meetingPoint(head).val
                + ", cycle starts at " + cycleStart(head).val);
    }
}

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


def meeting_point(head):
    """Phase 1: slow moves one step, fast two. Return where they meet, or None if the list ends."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # the same node, not just the same value
            return slow
    return None


def cycle_start(head):
    """Phase 2: one pointer from the head, one from the meeting point, one step each."""
    meet = meeting_point(head)
    if meet is None:
        return None
    a, b = head, meet
    while a is not b:  # both are mu steps from the loop's first node
        a = a.next
        b = b.next
    return a


nodes = [Node(v) for v in range(1, 7)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i + 1]
head = nodes[0]

print("Straight list: " + ("no cycle" if cycle_start(head) is None else "cycle"))

nodes[5].next = nodes[2]  # 6 now points back to 3
print(f"Tail linked back to 3: pointers meet at {meeting_point(head).val}, "
      f"cycle starts at {cycle_start(head).val}")

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

// Phase 1: slow moves one step, fast two. Returns where they meet, or null if the list ends.
function meetingPoint(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return slow; // the same node, not just the same value
  }
  return null;
}

// Phase 2: one pointer from the head, one from the meeting point, one step each.
function cycleStart(head) {
  const meet = meetingPoint(head);
  if (meet === null) return null;
  let a = head;
  let b = meet;
  while (a !== b) {
    // both are mu steps from the loop's first node
    a = a.next;
    b = b.next;
  }
  return a;
}

const nodes = [];
for (let v = 1; v <= 6; v++) nodes.push(new Node(v));
for (let i = 0; i + 1 < nodes.length; i++) nodes[i].next = nodes[i + 1];
const head = nodes[0];

console.log("Straight list: " + (cycleStart(head) === null ? "no cycle" : "cycle"));

nodes[5].next = nodes[2]; // 6 now points back to 3
console.log(`Tail linked back to 3: pointers meet at ${meetingPoint(head).val}, cycle starts at ${cycleStart(head).val}`);

Straight list: no cycle
Tail linked back to 3: pointers meet at 5, cycle starts at 3

Floyd's algorithm works wherever each item decides the next one. Happy Number detects the loop of digit-square sums without storing them, and Find the Duplicate Number reads index i as a node whose next is nums[i]: the duplicate has two arrows into it, so it is where the loop starts.

Merging two sorted lists

Keep a pointer into each sorted list and a tail for the result, starting at a dummy head, and repeatedly link the smaller front node after tail.

1. Two sorted lists, 1 → 4 → 5 → null and 2 → 3 → 6 → 8 → null. The merged list starts at a dummy node D, and tail marks its last node. No new nodes are made: the existing ones are re-linked.
2. Compare the two front nodes: 1 is smaller than 2, so tail.next = that node, tail moves onto it and a moves on. Thanks to the dummy, the first node taken needs no special case.
3. 2 against 4: 2 is smaller, so it is linked after tail and b moves on.
4. 3 against 4: 3 is smaller, so it is linked after tail and b moves on.
5. 4 against 6: 4 is smaller, so it is linked after tail and a moves on.
6. 5 against 6: 5 is smaller, so it is linked after tail and a moves on.
7. a is empty. The rest of b, 6 → 8, is already sorted and already linked, so one write attaches all of it: tail.next = b. An array merge would copy each element.
8. dummy.next is the merged list, 1 → 2 → 3 → 4 → 5 → 6 → 8 → null: O(n + m) time and O(1) extra space. Taking from a on a tie keeps equal values in their original order, and this loop is the merge step of merge sort on lists.

The leftover run is attached with one write instead of being copied: O(n + m) time, O(1) extra space. It is the merge step of merge sort, the usual way to sort a list — see Sorting Algorithms.

Linked lists in each language

C++ has std::list and std::forward_list, Java has java.util.LinkedList, and Python and JavaScript have none, so you write a small node class. Interviews hand you the node class and the head and expect you to rewire the pointers yourself; copying the values into an array skips the skill being tested.

Time and space complexity

How to recognise a linked-list problem

• A ListNode and a head, in place: rewire pointers, with a dummy head.
• Reverse all or part of a list: the three-pointer loop.
• Middle, split in half or palindrome: fast and slow pointers, then often reverse the second half.
• Cycle, loop, or a sequence where each value decides the next: Floyd's algorithm.
• The k-th node from the end: two pointers k nodes apart, moving together.

If you only ever work at the ends, you are really using a stack or a queue.

Common mistakes

• Losing the rest of the list: overwriting cur.next before saving it.
• Dereferencing null: fast.next.next when fast or fast.next is null.
• Special-casing the head, and getting it wrong: use a dummy head.
• Comparing values instead of nodes in cycle detection.
• Creating a cycle by accident: the new last node must point to null.
• Indexing a library list in a loop: Java's LinkedList.get(i) makes an O(n) pass O(n²).

Practice in this order

The judge passes arrays and numbers, not nodes, so these practise the same ideas on arrays:

1. Reverse String: reversal in place.
2. Remove Element: deleting as you walk.
3. Merge Sorted Array: the merge loop, one pointer per input.
4. Happy Number: Floyd's cycle detection on numbers.
5. Rotate Array: on a list, join the tail to the head and cut k nodes from the end.
6. Find the Winner of the Circular Game: a circular list, re-linked at each removal.
7. Find the Duplicate Number: both phases of Floyd's algorithm.

Fast and slow pointers belong to the two pointers family; the two pointers problem list has more. Next is the stack.