// Linked Lists

core idea

A linked list only moves forward, so the craft here is holding the right pointers at the right moment instead of indexing wherever you like. Three moves cover almost everything: run two pointers at different speeds to learn about the list’s structure without knowing its length, park a throwaway node in front of the real head so “is this the first node?” stops being a special case, and reverse arrows in place instead of copying data. Every problem below is one or two of these chained together.

when to reach for it

• The question needs a position relative to the list’s length (middle, kth-from-the-end) without a length you’re handed up front → fast/slow, or a fixed-gap pointer pair.
• The head might change — you’re deleting the first node, merging two lists, or building a brand-new one → a dummy head erases that branch entirely.
• The words reverse, reorder, or “in groups of k” show up → walk with prev/curr/next and flip arrows as you go.
• The problem looks like two of the above stacked — find the middle, then reverse, then compare — that combo is common enough to be its own shape: palindrome-style.

universal templates

All three skeletons below share one node type — the standard interview definition you’ll see in every solution on this site:

public class ListNode(int val = 0, ListNode? next = null)
{
    public int Val = val;
    public ListNode? Next = next;
}

Fast / slow — learns the list’s shape in one pass:

public ListNode? FastSlow(ListNode? head)
{
    ListNode? slow = head, fast = head;
    while (fast != null && fast.Next != null)   // fast dies first — checked so slow never overruns
    {
        slow = slow!.Next;                       // one step
        fast = fast.Next.Next;                   // two steps — the 2x gap is the whole trick
    }
    return slow;                                 // middle when it stops; meeting point if a cycle exists
}

Dummy head — the workhorse for anything that builds or mutates a list:

public ListNode? BuildOrMutate(ListNode? head)
{
    var dummy = new ListNode(0, head);   // one throwaway node erases "is this the first node?"
    var tail = dummy;                    // walk and mutate from here — tail.Next is always writable

    // ... build/merge/delete logic reads and writes through tail.Next ...

    return dummy.Next;                   // the dummy itself is never part of the answer
}

Iterative reversal — flip arrows instead of copying values:

public ListNode? Reverse(ListNode? head)
{
    ListNode? prev = null;
    ListNode? curr = head;
    while (curr != null)
    {
        ListNode? next = curr.Next;   // save before you overwrite it
        curr.Next = prev;             // flip the arrow
        prev = curr;                  // advance prev
        curr = next;                  // advance curr
    }
    return prev;                      // prev is the new head once curr runs off the end
}

Every problem below is one of these three skeletons — or two of them, run back to back.

problems

Two warm-ups on fast/slow, two dummy-head workhorses, and three combo problems that chain this topic’s pieces together — capped by the classic hashmap + linked-list design question.

1. 01Middle of the Linked ListeasyLC #876▶ interactive

   Fast at 2× speed ⇒ slow at the middle when fast hits the end.

2. 02Linked List CycleeasyLC #141

   Fast catches slow on a circular track ⇒ cycle exists — and why they must meet.

3. 03Reverse Linked ListeasyLC #206▶ interactive

   Save next, flip arrow, advance — the four-line mantra.

4. 04Merge Two Sorted ListseasyLC #21

   Dummy head + tail pointer: stitch the smaller node on, repeat.

5. 05Add Two NumbersmediumLC #2

   Dummy head again, plus the carry idiom — a top-ten interview question.

6. 06Remove Nth Node From EndmediumLC #19

   Gap-of-n pointers + dummy head to survive removing the first node.

7. 07Palindrome Linked ListeasyLC #234

   Combo: find middle, reverse second half, mirror-compare.

8. 08LRU CachemediumLC #146stretch

   The classic design combo: hashmap + doubly linked list (hand-rolled and LinkedList<T>).