Linked Lists in C#: Two Pointers That Move at Different Speeds

Parts 1 to 10 are contest patterns. From here the series covers the interview ones, and the first thing to say about linked lists is that you will almost never see one in a contest. Codeforces hands you an array. Interviews hand you a linked list constantly.

The second thing is a C# problem. LinkedList<T> exists in the BCL and is doubly linked, exposing LinkedListNode<T> with both Next and Previous. That is not the structure these problems are about, and using it removes the difficulty rather than solving it. Every program here declares its own node:

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

That is a primary constructor, and it is the whole type. Every program below is complete, was run on .NET 10, and its output is pasted from the run.

Pattern 51 — The middle, in one pass

The obvious approach walks the list to count it, then walks half of it again. Two passes, and you need the length.

Instead move two pointers, one twice as fast. When the fast one reaches the end, the slow one is halfway.

// C# has no singly-linked node type. LinkedList<T> is DOUBLY linked, exposes
// LinkedListNode<T>, and is not what an interview hands you. Declare your own.
static ListNode? Build(params int[] values)
{
    ListNode? head = null;
    for (int i = values.Length - 1; i >= 0; i--) head = new ListNode(values[i], head);
    return head;
}

static string Show(ListNode? n)
{
    var parts = new List<string>();
    for (; n is not null; n = n.Next) parts.Add(n.Value.ToString());
    return string.Join(" -> ", parts);
}

// Two pointers, one moving twice as fast. When fast runs out, slow is halfway.
static ListNode? Middle(ListNode? head, bool secondOfTwo)
{
    ListNode? slow = head, fast = head;
    while (secondOfTwo
        ? fast is not null && fast.Next is not null            // stops later
        : fast?.Next is not null && fast.Next.Next is not null) // stops earlier
    {
        slow = slow!.Next;
        fast = fast!.Next!.Next;
    }
    return slow;
}

foreach (int[] vals in new[] { new[] { 1, 2, 3, 4, 5 }, new[] { 1, 2, 3, 4, 5, 6 } })
{
    var head = Build(vals);
    Console.WriteLine($"{Show(head),-24}  length {vals.Length}");
    Console.WriteLine($"    first of two  -> {Middle(head, false)!.Value}");
    Console.WriteLine($"    second of two -> {Middle(head, true)!.Value}");
}

Console.WriteLine("\nOdd length has one middle and both agree. Even length has two,");
Console.WriteLine("and the loop condition alone decides which one you get.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

It prints:

1 -> 2 -> 3 -> 4 -> 5     length 5
    first of two  -> 3
    second of two -> 3
1 -> 2 -> 3 -> 4 -> 5 -> 6  length 6
    first of two  -> 3
    second of two -> 4

Odd length has one middle and both agree. Even length has two,
and the loop condition alone decides which one you get.

The detail people get wrong is that an even-length list has two middles, and nothing in the code names which you want — the loop condition alone decides. while (fast?.Next is not null && fast.Next.Next is not null) stops earlier and gives you the first; while (fast is not null && fast.Next is not null) gives you the second.

Read the problem statement carefully, then pick the condition. Do not pick a condition and hope.

Cost: O(n) time, O(1) space, one pass.

Reach for it when you need the middle, or need to split a list in half — merge sort on a linked list starts here.

Pattern 52 — Floyd’s cycle detection

Does the list loop back on itself? A HashSet<ListNode> answers it in O(n) memory. Two pointers answer it in none.

// Build a list whose tail loops back to index `enterAt`, or -1 for no cycle.
static ListNode Build(int n, int enterAt)
{
    var nodes = new ListNode[n];
    for (int i = 0; i < n; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < n - 1; i++) nodes[i].Next = nodes[i + 1];
    if (enterAt >= 0) nodes[n - 1].Next = nodes[enterAt];
    return nodes[0];
}

static bool HasCycle(ListNode head, bool trace)
{
    ListNode? slow = head, fast = head;
    int step = 0;
    while (fast is not null && fast.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        step++;
        if (trace) Console.WriteLine($"  step {step}: slow at {slow!.Value}, fast at {(fast is null ? "off the end" : fast.Value.ToString())}");
        if (ReferenceEquals(slow, fast))
        {
            if (trace) Console.WriteLine($"  they are the same node -> cycle");
            return true;
        }
    }
    if (trace) Console.WriteLine("  fast ran off the end -> no cycle");
    return false;
}

Console.WriteLine("6 nodes, tail links back to index 2 (the node holding 3):");
Console.WriteLine($"  cycle: {HasCycle(Build(6, 2), true)}");

Console.WriteLine("\n6 nodes, no cycle:");
Console.WriteLine($"  cycle: {HasCycle(Build(6, -1), true)}");

Console.WriteLine("\nWhy they must meet: inside the cycle, fast gains exactly one place on slow");
Console.WriteLine("per step. A gap that shrinks by one every step reaches zero. It cannot");
Console.WriteLine("step over slow, because stepping over means the gap went from 1 to -1,");
Console.WriteLine("and it only ever changes by 1.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

It prints:

6 nodes, tail links back to index 2 (the node holding 3):
  step 1: slow at 2, fast at 3
  step 2: slow at 3, fast at 5
  step 3: slow at 4, fast at 3
  step 4: slow at 5, fast at 5
  they are the same node -> cycle
  cycle: True

6 nodes, no cycle:
  step 1: slow at 2, fast at 3
  step 2: slow at 3, fast at 5
  step 3: slow at 4, fast at off the end
  fast ran off the end -> no cycle
  cycle: False

Why they must meet: inside the cycle, fast gains exactly one place on slow
per step. A gap that shrinks by one every step reaches zero. It cannot
step over slow, because stepping over means the gap went from 1 to -1,
and it only ever changes by 1.

The usual explanation is that the fast pointer “laps” the slow one. That is true and it is not a proof, because lapping does not obviously imply landing on the same node — it could step over.

The actual argument is in the last three lines of that output. Once both pointers are inside the cycle, each step moves slow by one and fast by two, so the gap between them changes by exactly one per step. A quantity that changes by one at a time and is heading towards zero must hit zero. It cannot jump from 1 to −1.

Note also ReferenceEquals rather than ==. On a custom class == is reference equality anyway, but writing it explicitly says you meant the same node, not a node with the same value — and the moment someone adds an Equals override, the explicit version keeps working.

Cost: O(n) time, O(1) space.

Reach for it when anything might loop and you cannot afford a visited set. It generalises past linked lists: Happy Number and Find the Duplicate Number are both this pattern with “next” defined by a function instead of a pointer.

Pattern 53 — Where the cycle starts

Detecting a loop is half the question. Finding the node where it begins looks like it needs bookkeeping, and it needs two lines.

Reset one pointer to the head. Advance both, one step at a time. They meet at the entry.

static ListNode Build(int n, int enterAt, out ListNode entry)
{
    var nodes = new ListNode[n];
    for (int i = 0; i < n; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < n - 1; i++) nodes[i].Next = nodes[i + 1];
    nodes[n - 1].Next = nodes[enterAt];
    entry = nodes[enterAt];
    return nodes[0];
}

int n = 9, enterAt = 3;
ListNode head = Build(n, enterAt, out ListNode realEntry);
int tail = enterAt, cycle = n - enterAt;
Console.WriteLine($"{n} nodes, cycle starts at index {enterAt} (value {realEntry.Value})");
Console.WriteLine($"  L = {tail} nodes before the cycle, C = {cycle} nodes in it\n");

// Phase 1: find any meeting point inside the cycle.
ListNode slow = head, fast = head;
int steps = 0;
do { slow = slow.Next!; fast = fast.Next!.Next!; steps++; }
while (!ReferenceEquals(slow, fast));
Console.WriteLine($"phase 1: met at value {slow.Value} after {steps} steps");
Console.WriteLine($"  slow travelled {steps}, fast travelled {steps * 2}");
Console.WriteLine($"  fast went round the cycle {(steps * 2 - steps) / cycle} extra time(s)\n");

// Phase 2: reset one pointer to the head, then advance BOTH one at a time.
ListNode a = head;
int walk = 0;
while (!ReferenceEquals(a, slow)) { a = a.Next!; slow = slow.Next!; walk++; }
Console.WriteLine($"phase 2: reset one to head, step both by 1");
Console.WriteLine($"  met again after {walk} steps, at value {a.Value}");
Console.WriteLine($"  correct: {ReferenceEquals(a, realEntry)}");

Console.WriteLine($"\nWhy: at the meeting point slow has walked L + k, and fast twice that.");
Console.WriteLine($"So 2(L + k) = L + k + nC, giving L + k = nC, so L = nC - k.");
Console.WriteLine($"Walking L more steps from the meeting point lands exactly on the entry.");
Console.WriteLine($"Here L = {tail} and the phase-2 walk took {walk} steps.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

It prints:

9 nodes, cycle starts at index 3 (value 4)
  L = 3 nodes before the cycle, C = 6 nodes in it

phase 1: met at value 7 after 6 steps
  slow travelled 6, fast travelled 12
  fast went round the cycle 1 extra time(s)

phase 2: reset one to head, step both by 1
  met again after 3 steps, at value 4
  correct: True

Why: at the meeting point slow has walked L + k, and fast twice that.
So 2(L + k) = L + k + nC, giving L + k = nC, so L = nC - k.
Walking L more steps from the meeting point lands exactly on the entry.
Here L = 3 and the phase-2 walk took 3 steps.

That looks like a trick until the arithmetic is written down. Let L be the number of nodes before the cycle and C the cycle length. At the meeting point, slow has taken L + k steps for some k inside the cycle, and fast has taken twice that. Fast has also gone round n extra times, so:

2(L + k) = L + k + nC
    L + k = nC
        L = nC − k

Walking L more steps from the meeting point covers k + L = nC steps in total — a whole number of laps — so it lands exactly on the entry. In the run above L = 3 and the second phase took exactly 3 steps.

Cost: O(n) time, O(1) space.

Reach for it when the problem asks where the cycle begins, or for the duplicate value in an array of n+1 values from 1..n — which is this pattern with the array as the “next” function.

Pattern 54 — Reversing in place

Three pointers, and one line that must come first.

static ListNode? Build(params int[] v)
{
    ListNode? head = null;
    for (int i = v.Length - 1; i >= 0; i--) head = new ListNode(v[i], head);
    return head;
}
static string Show(ListNode? n)
{
    var p = new List<string>();
    for (; n is not null; n = n.Next) p.Add(n.Value.ToString());
    return string.Join(" -> ", p);
}

// Three pointers. Every step re-points ONE arrow backwards.
static ListNode? Reverse(ListNode? head, bool trace)
{
    ListNode? prev = null, cur = head;
    while (cur is not null)
    {
        ListNode? next = cur.Next;      // save it FIRST — the next line destroys it
        cur.Next = prev;                // flip the arrow
        prev = cur;                     // shuffle both forward
        cur = next;
        if (trace) Console.WriteLine($"    reversed=[{Show(prev)}]   remaining=[{Show(cur)}]");
    }
    return prev;                        // cur is null; prev is the new head
}

Console.WriteLine($"start: {Show(Build(1, 2, 3, 4, 5))}");
Console.WriteLine("reversing:");
var r = Reverse(Build(1, 2, 3, 4, 5), true);
Console.WriteLine($"result: {Show(r)}\n");

// Reverse only positions m..n (1-based). The dummy head removes the special
// case where m == 1 and the list head itself changes.
static ListNode? ReverseBetween(ListNode? head, int m, int n)
{
    var dummy = new ListNode(0, head);
    ListNode before = dummy;
    for (int i = 1; i < m; i++) before = before.Next!;

    ListNode? prev = null, cur = before.Next;
    for (int i = 0; i <= n - m; i++)
    {
        ListNode? next = cur!.Next;
        cur.Next = prev; prev = cur; cur = next;
    }
    before.Next!.Next = cur;    // the old first node is now last in the section
    before.Next = prev;         // and prev is now first
    return dummy.Next;
}

Console.WriteLine($"reverse positions 2..4: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 2, 4))}");
Console.WriteLine($"reverse positions 1..5: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 1, 5))}");
Console.WriteLine($"reverse positions 1..1: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 1, 1))}");

// In groups of k, leaving any short final group alone.
static ListNode? ReverseKGroup(ListNode? head, int k)
{
    ListNode? check = head;
    for (int i = 0; i < k; i++) { if (check is null) return head; check = check.Next; }

    ListNode? prev = null, cur = head;
    for (int i = 0; i < k; i++) { ListNode? nx = cur!.Next; cur.Next = prev; prev = cur; cur = nx; }
    head!.Next = ReverseKGroup(cur, k);   // head is now the tail of this group
    return prev;
}

Console.WriteLine();
foreach (int k in new[] { 2, 3, 5, 6 })
    Console.WriteLine($"k={k}: {Show(ReverseKGroup(Build(1, 2, 3, 4, 5), k))}");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

It prints:

start: 1 -> 2 -> 3 -> 4 -> 5
reversing:
    reversed=[1]   remaining=[2 -> 3 -> 4 -> 5]
    reversed=[2 -> 1]   remaining=[3 -> 4 -> 5]
    reversed=[3 -> 2 -> 1]   remaining=[4 -> 5]
    reversed=[4 -> 3 -> 2 -> 1]   remaining=[5]
    reversed=[5 -> 4 -> 3 -> 2 -> 1]   remaining=[]
result: 5 -> 4 -> 3 -> 2 -> 1

reverse positions 2..4: 1 -> 4 -> 3 -> 2 -> 5
reverse positions 1..5: 5 -> 4 -> 3 -> 2 -> 1
reverse positions 1..1: 1 -> 2 -> 3 -> 4 -> 5

k=2: 2 -> 1 -> 4 -> 3 -> 5
k=3: 3 -> 2 -> 1 -> 4 -> 5
k=5: 5 -> 4 -> 3 -> 2 -> 1
k=6: 1 -> 2 -> 3 -> 4 -> 5

ListNode? next = cur.Next; must come before cur.Next = prev;. The second line destroys the only pointer to the rest of the list. Swap them and there is no exception and no crash — the list just ends early, and it looks like a logic bug somewhere else entirely.

At the end, cur is null and prev is the new head. Returning cur is the other classic slip.

The sublist version shows why the dummy head matters, which is the next pattern. ReverseBetween(list, 1, 5) reverses from the very first node, so the head of the list changes — and with a dummy in front, that is not a special case at all. Note 1..1 correctly does nothing.

The k-group version recurses on the remainder. After reversing a group, head is that group’s tail, which is exactly where the next group attaches.

Cost: O(n) time, O(1) space for the iterative versions.

Reach for it when you need a list reversed, partially reversed, rotated, or checked for being a palindrome — that last one is pattern 51 to find the middle, then this to reverse the back half.

Pattern 55 — The dummy head

A node that holds nothing, sitting in front of the real list, purely so that “the first node” is never a special case.

static ListNode? Build(params int[] v)
{
    ListNode? head = null;
    for (int i = v.Length - 1; i >= 0; i--) head = new ListNode(v[i], head);
    return head;
}
static string Show(ListNode? n)
{
    var p = new List<string>();
    for (; n is not null; n = n.Next) p.Add(n.Value.ToString());
    return p.Count == 0 ? "(empty)" : string.Join(" -> ", p);
}

// WITHOUT a dummy head: the first node is a special case, because there is no
// previous node to attach it to.
static ListNode? MergeAwkward(ListNode? a, ListNode? b)
{
    if (a is null) return b;
    if (b is null) return a;

    ListNode head, tail;
    if (a.Value <= b.Value) { head = tail = a; a = a.Next; }
    else                    { head = tail = b; b = b.Next; }

    while (a is not null && b is not null)
    {
        if (a.Value <= b.Value) { tail.Next = a; a = a.Next; }
        else                    { tail.Next = b; b = b.Next; }
        tail = tail.Next!;
    }
    tail.Next = a ?? b;
    return head;
}

// WITH a dummy head: no special case at all. Every node is attached the same way.
static ListNode? Merge(ListNode? a, ListNode? b)
{
    var dummy = new ListNode(0);
    ListNode tail = dummy;

    while (a is not null && b is not null)
    {
        if (a.Value <= b.Value) { tail.Next = a; a = a.Next; }
        else                    { tail.Next = b; b = b.Next; }
        tail = tail.Next!;
    }
    tail.Next = a ?? b;      // whichever still has nodes; both null is fine too
    return dummy.Next;       // the real head, whatever it turned out to be
}

Console.WriteLine($"a = {Show(Build(1, 3, 5, 7))}");
Console.WriteLine($"b = {Show(Build(2, 3, 6))}");
Console.WriteLine($"merged (dummy head) = {Show(Merge(Build(1, 3, 5, 7), Build(2, 3, 6)))}");
Console.WriteLine($"merged (awkward)    = {Show(MergeAwkward(Build(1, 3, 5, 7), Build(2, 3, 6)))}");
Console.WriteLine();
Console.WriteLine($"empty + [1,2]  = {Show(Merge(null, Build(1, 2)))}");
Console.WriteLine($"empty + empty  = {Show(Merge(null, null))}");
Console.WriteLine();
Console.WriteLine("The dummy version is four lines shorter and has no branch for the");
Console.WriteLine("first node. Both null works too, because dummy.Next was never set.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

It prints:

a = 1 -> 3 -> 5 -> 7
b = 2 -> 3 -> 6
merged (dummy head) = 1 -> 2 -> 3 -> 3 -> 5 -> 6 -> 7
merged (awkward)    = 1 -> 2 -> 3 -> 3 -> 5 -> 6 -> 7

empty + [1,2]  = 1 -> 2
empty + empty  = (empty)

The dummy version is four lines shorter and has no branch for the
first node. Both null works too, because dummy.Next was never set.

Both functions in that program produce identical output. The difference is that the awkward one needs a branch to decide the head before the loop can start, and then repeats the comparison it just made. The dummy version attaches every node the same way and returns dummy.Next at the end — whatever that turned out to be.

It also handles the empty cases for free. Merge(null, null) returns dummy.Next, which was never assigned, which is null. No guard needed.

Cost: one extra node, and it is garbage the moment you return.

Reach for it when a list operation might change the head — merging, deleting a node, removing the nth from the end, partitioning around a value. If you find yourself writing if (head == null) followed by a duplicated first iteration, that is the signal.

What to remember

• LinkedList<T> is doubly linked and is not what these problems mean. Declare a four-line ListNode and move on.

• The fast pointer’s loop condition picks which middle you get. On an even-length list there are two, and the code does not otherwise say which one you wanted.

• The proof that Floyd’s terminates is that the gap changes by exactly one. Not “it laps eventually” — that does not rule out stepping over.

• L = nC − k is why phase two lands on the entry. Reset one pointer to the head, step both by one.

• Save next before you overwrite cur.Next. Getting this backwards truncates the list silently, with no exception to point at the line.

• Return prev, not cur. At the end of a reversal cur is null.

• A dummy head deletes the special case, not just tidies it. If you are writing a separate branch for the first node, add a dummy and delete the branch.

Part 12 starts on trees: the four traversal orders, the iterative one people cannot reconstruct under pressure, and why level-order needs a queue rather than cleverness.