Find Middle Element of Linked List in DSA C#

Mental Model

To find the middle, move two pointers at different speeds; when the fast one reaches the end, the slow one is in the middle.

Analogy: Imagine two friends walking on a path: one walks twice as fast as the other. When the faster friend reaches the end, the slower friend is exactly halfway.

Head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
Slow ↑
Fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, find middle element

Goal: Find the middle node value of the linked list

Step 1: Initialize slow and fast pointers at head (node 1)

Head -> [Slow->1, Fast->1] -> 2 -> 3 -> 4 -> 5 -> null

Why: Start both pointers at the beginning to begin traversal

Step 2: Move slow by 1 step to node 2, fast by 2 steps to node 3

Head -> 1 -> [Slow->2] -> [Fast->3] -> 4 -> 5 -> null

Why: Slow moves one step, fast moves two steps to find middle efficiently

Step 3: Move slow by 1 step to node 3, fast by 2 steps to node 5

Head -> 1 -> 2 -> [Slow->3] -> 4 -> [Fast->5] -> null

Why: Continue moving pointers until fast reaches the end

Step 4: Fast cannot move two steps further (end reached), stop

Head -> 1 -> 2 -> [Slow->3] -> 4 -> 5 -> null

Why: Fast pointer reached the end, slow pointer is at middle

Result:

1 -> 2 -> [3] -> 4 -> 5 -> null
Middle element value is 3

Annotated Code

DSA C#

using System;

public class Node
{
    public int data;
    public Node next;

    public Node(int data)
    {
        this.data = data;
        this.next = null;
    }
}

public class LinkedList
{
    public Node head;

    public void AddLast(int data)
    {
        Node newNode = new Node(data);
        if (head == null)
        {
            head = newNode;
            return;
        }
        Node curr = head;
        while (curr.next != null)
        {
            curr = curr.next;
        }
        curr.next = newNode;
    }

    public int FindMiddle()
    {
        if (head == null)
            throw new InvalidOperationException("List is empty");

        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null)
        {
            slow = slow.next; // move slow by 1
            fast = fast.next.next; // move fast by 2
        }

        return slow.data; // slow is at middle
    }

    public override string ToString()
    {
        Node curr = head;
        string result = "";
        while (curr != null)
        {
            result += curr.data + " -> ";
            curr = curr.next;
        }
        result += "null";
        return result;
    }
}

public class Program
{
    public static void Main()
    {
        LinkedList list = new LinkedList();
        list.AddLast(1);
        list.AddLast(2);
        list.AddLast(3);
        list.AddLast(4);
        list.AddLast(5);

        Console.WriteLine(list.ToString());
        int middle = list.FindMiddle();
        Console.WriteLine("Middle element value is " + middle);
    }
}

Node slow = head; Node fast = head;

Initialize two pointers at the start of the list

while (fast != null && fast.next != null) { slow = slow.next; // move slow by 1 fast = fast.next.next; // move fast by 2 }

Move slow by one and fast by two until fast reaches the end

return slow.data; // slow is at middle

Return the data at slow pointer which is the middle element

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Middle element value is 3

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Compared to counting nodes first then traversing half, this method finds middle in one pass saving time

Edge Cases

empty list

throws InvalidOperationException indicating list is empty

DSA C#

if (head == null)
    throw new InvalidOperationException("List is empty");

list with one element

returns the single element as middle

DSA C#

while (fast != null && fast.next != null)

list with even number of elements

returns the second middle element (e.g., for 4 elements returns 3rd node)

DSA C#

while (fast != null && fast.next != null)

When to Use This Pattern

When you need to find the middle of a linked list efficiently, use two pointers moving at different speeds to find it in one pass.

Common Mistakes

Mistake: Moving both pointers by one step instead of fast pointer by two
Fix: Move fast pointer by two steps inside the loop to reach the end faster

Mistake: Not checking if fast or fast.next is null before moving fast pointer
Fix: Add condition 'fast != null && fast.next != null' in while loop to avoid null reference

Summary

Finds the middle element of a linked list using two pointers.

Use when you want the middle node without counting total nodes first.

The slow pointer moves half as fast as the fast pointer, so it lands in the middle when fast reaches the end.

Practice

1. What is the main idea behind finding the middle element of a singly linked list using the two-pointer technique?

easy

A. Reverse the list and pick the first element

B. Count all nodes first, then access the middle by index

C. Use two pointers moving at the same speed until they meet

D. Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end

Solution

1. Step 1: Understand two-pointer movement

   The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.

2. Step 2: Identify middle when fast pointer ends

   When the fast pointer reaches the end (null), the slow pointer will be at the middle node.

3. Final Answer:

   Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end -> Option D

4. Quick Check:

   Two-pointer technique = slow one step, fast two steps [OK]

Hint: Move fast pointer twice as fast as slow to find middle [OK]

Common Mistakes:

• Moving both pointers at the same speed
• Not checking for null before moving fast pointer
• Counting nodes first instead of using pointers

2. Which of the following C# code snippets correctly initializes two pointers to find the middle of a linked list named head?

easy

A. ListNode slow = head; ListNode fast = head;

B. ListNode slow = null; ListNode fast = head;

C. ListNode slow = head.next; ListNode fast = head.next.next;

D. ListNode slow = head; ListNode fast = null;

Solution

1. Step 1: Check pointer initialization

   Both slow and fast pointers should start at the head of the list to traverse correctly.

2. Step 2: Validate options

   Only ListNode slow = head; ListNode fast = head; initializes both pointers at head, allowing proper traversal.

3. Final Answer:

   ListNode slow = head; ListNode fast = head; -> Option A

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head to traverse linked list [OK]

Common Mistakes:

• Starting slow or fast pointer at null
• Starting fast pointer too far ahead causing null errors
• Using head.next without checking for null

3. What will be the output of the following C# code that finds the middle element of a linked list?

class ListNode {
  public int val;
  public ListNode next;
  public ListNode(int x) { val = x; next = null; }
}

ListNode head = new ListNode(10);
head.next = new ListNode(20);
head.next.next = new ListNode(30);
head.next.next.next = new ListNode(40);
head.next.next.next.next = new ListNode(50);

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
  slow = slow.next;
  fast = fast.next.next;
}
Console.WriteLine(slow.val);

medium

A. 30

B. 20

C. 40

D. 50

Solution

1. Step 1: Trace pointer movement

   Initial: slow=10, fast=10
   Iteration 1: slow=20, fast=30
   Iteration 2: slow=30, fast=50
   Iteration 3: fast.next is null, loop ends.

2. Step 2: Identify middle element

   Slow pointer is at node with value 30, which is the middle of the list.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Middle element = 30 [OK]

Hint: Slow pointer lands on middle when fast reaches end [OK]

Common Mistakes:

• Assuming middle is 20 or 40 without tracing
• Not checking fast.next before moving fast
• Confusing slow and fast pointer positions

4. The following code is intended to find the middle element of a linked list but throws a NullReferenceException. What is the error?

ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
  slow = slow.next;
  fast = fast.next.next;
}
Console.WriteLine(slow.val);

medium

A. The fast pointer should start at head.next

B. The slow pointer should move two steps instead of one

C. The while condition should check if fast is null before fast.next

D. The loop should run while fast != null only

Solution

1. Step 1: Analyze while loop condition

   The condition checks fast.next and fast.next.next but does not check if fast itself is null, which can cause NullReferenceException.

2. Step 2: Correct condition order

   Check if fast != null before accessing fast.next to avoid exceptions.

3. Final Answer:

   The while condition should check if fast is null before fast.next -> Option C

4. Quick Check:

   Check fast != null before fast.next to avoid errors [OK]

Hint: Always check pointer is not null before accessing next [OK]

Common Mistakes:

• Checking fast.next before fast itself
• Moving slow pointer incorrectly
• Starting fast pointer at wrong node

5. Given a singly linked list with an even number of nodes, how can you modify the two-pointer approach to return the first middle node instead of the second middle node?

hard

A. Move slow pointer two steps and fast pointer one step in the loop

B. Start fast pointer at head.next and slow at head, with the usual loop condition

C. Change the loop condition to 'while (fast.next != null && fast.next.next != null)' and move slow inside the loop

D. Use a stack to store nodes and pop half to get the first middle

Solution

1. Step 1: Understand default behavior

   Normally, the two-pointer method returns the second middle node for even-length lists.

2. Step 2: Modify pointer start positions

   Starting the fast pointer at head.next and slow at head with the usual loop condition causes the slow pointer to stop at the first middle node.

3. Final Answer:

   Start fast pointer at head.next and slow at head, with the usual loop condition -> Option B

4. Quick Check:

   Adjust pointer start positions to get first middle [OK]

Hint: Start fast one step ahead to get first middle [OK]

Common Mistakes:

• Swapping slow and fast pointer speeds incorrectly
• Starting fast pointer at wrong node
• Using extra data structures unnecessarily