Find Middle Element of Linked List in DSA C# - Execution Trace

Concept Flow - Find Middle Element of Linked List

Start at head

↓

Initialize two pointers: slow, fast

↓

Check: fast != null and fast.next != null?

No→Stop

Yes↓

Move slow by 1 node

↓

Move fast by 2 nodes

↓

Repeat check

Back to Check↓

slow now points to middle node

↓

Return slow

↓

Done

↩Back to Check

Two pointers move through the list: slow moves one step, fast moves two steps. When fast reaches the end, slow is at the middle.

Execution Sample

DSA C#

Node FindMiddle(Node head) {
  Node slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

Finds the middle node of a linked list by moving slow pointer one step and fast pointer two steps until fast reaches the end.

Execution Table

Step	Operation	slow Pointer	fast Pointer	Visual State	Notes
1	Initialize slow and fast to head	Node 10	Node 10	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head	Start both pointers at head node
2	Check fast and fast.next not null	Node 10	Node 10	Same as above	Condition true, enter loop
3	Move slow by 1 node	Node 20	Node 10	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow	Slow moves to second node
4	Move fast by 2 nodes	Node 20	Node 30	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast	Fast moves two nodes ahead
5	Check fast and fast.next not null	Node 20	Node 30	Same as above	Condition true, continue loop
6	Move slow by 1 node	Node 30	Node 30	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast	Slow moves to third node
7	Move fast by 2 nodes	Node 30	Node 50	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast	Fast moves two nodes ahead
8	Check fast and fast.next not null	Node 30	Node 50	Same as above	fast.next is null, condition false, exit loop
9	Return slow as middle	Node 30	Node 50	Same as above	Middle node found (data: 30)

💡 Loop stops when fast reaches last node (fast.next == null), slow points to middle node

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 7	Final
slow	Node 10	Node 20	Node 30	Node 30	Node 30
fast	Node 10	Node 10	Node 30	Node 50	Node 50

Key Moments - 3 Insights

Why do we move fast pointer two steps but slow pointer only one step?

Moving fast pointer two steps ensures it reaches the end twice as fast as slow. When fast reaches the end, slow is exactly at the middle. See execution_table steps 3,4 and 6,7 for pointer movements.

What happens if the list has even number of nodes?

The slow pointer will stop at the first of the two middle nodes. For example, if list length is 6, slow will point to node 3 when fast reaches the end. This is because fast moves two steps and loop stops when fast or fast.next is null.

Why do we check both fast != null and fast.next != null in the loop condition?

We check both to avoid null reference errors when moving fast two steps. If fast or fast.next is null, moving fast.next.next would cause error. See execution_table step 8 where fast.next is null and loop stops.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, where is the slow pointer?

A Node 20

B Node 10

C Node 30

D Node 50

💡 Hint

Check the 'slow Pointer' column at step 6 in execution_table

At which step does the loop condition become false?

A Step 5

B Step 8

C Step 3

D Step 9

💡 Hint

Look at the 'Operation' and 'Notes' columns in execution_table for when fast.next is null

If the list had only one node, what would slow point to after initialization?

A head node

B null

C second node

D fast pointer

💡 Hint

Refer to variable_tracker start values and concept_flow initialization

Concept Snapshot

Find Middle Element of Linked List:
- Use two pointers: slow and fast starting at head
- Move slow by 1 node, fast by 2 nodes each loop
- Loop until fast or fast.next is null
- Slow pointer then points to middle node
- Works for odd and even length lists
- Time: O(n), Space: O(1)

Full Transcript

To find the middle element of a linked list, we use two pointers called slow and fast. Both start at the head node. In each step, slow moves one node forward, while fast moves two nodes forward. We keep doing this until fast reaches the end of the list or the node before the end. At that point, slow points to the middle node. This method works because fast moves twice as fast as slow, so when fast reaches the end, slow is halfway through. The code initializes slow and fast to head, then loops while fast and fast.next are not null, moving slow by one and fast by two nodes each time. Finally, slow is returned as the middle node. This approach works for lists with odd or even number of nodes and runs in linear time with constant space.

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