Find Middle Element of Linked List in DSA Java - Execution Trace

Concept Flow - Find Middle Element of Linked List

Start: head points to first node

↓

Initialize two pointers: slow and fast at head

↓

Loop: while fast != null and fast.next != null

↓

Move slow by one node

↓

Move fast by two nodes

↓

Repeat loop

↓

When loop ends, slow points to middle node

↓

Return slow.data as middle element

Use two pointers moving at different speeds to find the middle node in one pass.

Execution Sample

DSA Java

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

Two pointers traverse the list; slow moves one step, fast moves two steps until fast reaches end.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Linked List State	Visual State
1	Initialize slow and fast at head	Node(10)	Node(10)	10 -> 20 -> 30 -> 40 -> 50 -> null	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ slow, fast → head
2	Check fast and fast.next not null	Node(10)	Node(10)	Same as above	Pointers valid, continue loop
3	Move slow to next node	Node(20)	Node(10)	Same as above	slow → 20, fast → 10
4	Move fast two nodes ahead	Node(20)	Node(30)	Same as above	fast → 30
5	Check fast and fast.next not null	Node(20)	Node(30)	Same as above	Pointers valid, continue loop
6	Move slow to next node	Node(30)	Node(30)	Same as above	slow → 30
7	Move fast two nodes ahead	Node(30)	Node(50)	Same as above	fast → 50
8	Check fast and fast.next not null	Node(30)	Node(50)	Same as above	fast.next is null, loop ends
9	Return slow.data as middle element	Node(30)	Node(50)	Same as above	Middle element is 30

💡 fast reached last node (50), fast.next is null, loop ends; 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 two steps and slow one step ensures when fast reaches the end, slow is at the middle (see execution_table steps 3,4,6,7).

What happens if the list has even number of nodes?

The slow pointer will point to the second of the two middle nodes when the loop ends, because fast will become null (not shown here but similar logic applies).

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

To avoid null pointer errors when moving fast two steps ahead (see execution_table step 8 where fast.next is null, so loop stops).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which node is the slow pointer pointing to?

A Node with data 20

B Node with data 30

C Node with data 10

D Node with data 50

💡 Hint

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

At which step does the loop condition become false?

A Step 5

B Step 7

C Step 8

D Step 9

💡 Hint

Look at the 'Operation' and 'Visual State' columns in execution_table to see when fast.next is null

If the linked list had 6 nodes instead of 5, where would slow point at loop end?

A Node 4 (fourth node)

B Node 2 (second node)

C Node 3 (third node)

D Node 5 (fifth node)

💡 Hint

Recall slow moves one step, fast moves two steps; with even nodes slow ends at first middle or second middle depending on implementation

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 ends when fast or fast.next is null
- slow points to middle node
- Returns middle element in one pass
- Handles odd and even length lists

Full Transcript

To find the middle element of a linked list, we use two pointers called slow and fast. Both start at the head of the list. 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 there is no next node for fast. At that point, slow will be pointing to the middle node. This method works in one pass and handles lists with odd or even numbers of nodes. The execution table shows each step, how slow and fast move, and the linked list state. The key moments explain why fast moves twice as fast and why we check for null pointers to avoid errors.

Practice

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

easy

A. Use two pointers both moving one step at a time

B. Count all nodes first, then traverse half the count again

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

D. Reverse the list and pick the first element

Solution

1. Step 1: Understand the two-pointer technique

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

2. Step 2: Identify when to stop

   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 C

4. Quick Check:

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

Hint: Move fast pointer twice as fast as slow pointer [OK]

Common Mistakes:

• Moving both pointers at the same speed
• Counting nodes first then traversing again
• Stopping when slow pointer reaches null

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

easy

A. Node slow = head; Node fast = head;

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

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

D. Node slow = head; Node fast = head.next;

Solution

1. Step 1: Initialize both pointers at the start

   Both slow and fast pointers should start at the head node to cover the entire list.

2. Step 2: Check initialization correctness

   Node slow = head; Node fast = head; initializes both pointers to head, which is correct for the two-pointer approach.

3. Final Answer:

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

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head node [OK]

Common Mistakes:

• Starting slow pointer at null
• Starting fast pointer ahead causing null errors
• Skipping nodes at initialization

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

class Node {
  int data;
  Node next;
  Node(int d) { data = d; next = null; }
}

public class Test {
  public static void main(String[] args) {
    Node head = new Node(10);
    head.next = new Node(20);
    head.next.next = new Node(30);
    head.next.next.next = new Node(40);
    head.next.next.next.next = new Node(50);

    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    System.out.println(slow.data);
  }
}

medium

A. 40

B. 20

C. 50

D. 30

Solution

1. Step 1: Trace slow and fast pointers

   Initially, slow=10, fast=10. After first loop: slow=20, fast=30. Second loop: slow=30, fast=50. Third loop: fast.next is null, loop ends.

2. Step 2: Identify slow pointer position at loop end

   Slow pointer is at node with data 30, which is the middle element.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   Middle element = 30 [OK]

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

Common Mistakes:

• Printing fast pointer data instead of slow
• Off-by-one errors in loop condition
• Assuming middle is first or last node

4. Identify the error in the following code snippet that attempts to find the middle element of a linked list and fix it:

Node slow = head;
Node fast = head.next;
while (fast != null && fast.next != null) {
  slow = slow.next;
  fast = fast.next.next;
}
System.out.println(slow.data);

medium

A. Print fast.data instead of slow.data

B. Initialize fast pointer to head instead of head.next

C. Move slow pointer two steps instead of one

D. Change while condition to only check fast != null

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer starts at head.next, which causes the slow pointer to point to the first middle in even-length lists.

2. Step 2: Correct initialization for consistent middle

   Initialize fast pointer at head to find the second middle element in even-length lists.

3. Final Answer:

   Initialize fast pointer to head instead of head.next -> Option B

4. Quick Check:

   Fast pointer starts at head for correct middle [OK]

Hint: Start fast pointer at head for correct middle [OK]

Common Mistakes:

• Starting fast pointer at head.next causing off-by-one
• Incorrect loop condition causing null pointer
• Moving slow pointer incorrectly

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 element instead of the second?

hard

A. Initialize fast pointer to head.next and use the same loop condition

B. Initialize slow pointer to head.next and fast pointer to head

C. Change loop condition to fast.next != null

D. Move slow pointer two steps and fast pointer one step

Solution

1. Step 1: Understand default behavior

   Starting both pointers at head returns the second middle in even-length lists.

2. Step 2: Modify initialization to get first middle

   Starting fast pointer at head.next causes slow pointer to land on the first middle.

3. Final Answer:

   Initialize fast pointer to head.next and use the same loop condition -> Option A

4. Quick Check:

   Fast starts at head.next for first middle [OK]

Hint: Start fast pointer one step ahead for first middle [OK]

Common Mistakes:

• Changing loop condition incorrectly
• Moving pointers in wrong directions
• Starting slow pointer ahead causing errors