Find Middle Element of Linked List in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the middle element output

What is the output of the following Java code that finds the middle element of a linked list?

DSA Java

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

public class LinkedList {
    Node head;

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

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(10);
        list.head.next = new Node(20);
        list.head.next.next = new Node(30);
        list.head.next.next.next = new Node(40);
        list.head.next.next.next.next = new Node(50);
        System.out.println(list.findMiddle());
    }
}

A 30

B 20

C 40

D 50

💡 Hint

Use two pointers: one moves twice as fast as the other.

The slow pointer moves one step at a time, the fast pointer moves two steps. When fast reaches the end, slow is at the middle. For 5 nodes, middle is the 3rd node with value 30.

❓ Predict Output

intermediate

Middle element with even number of nodes

What will be the output of the code when the linked list has an even number of nodes?

DSA Java

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

public class LinkedList {
    Node head;

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

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(10);
        list.head.next = new Node(20);
        list.head.next.next = new Node(30);
        list.head.next.next.next = new Node(40);
        System.out.println(list.findMiddle());
    }
}

A 20

B 10

C 40

D 30

💡 Hint

For even nodes, the slow pointer ends at the second middle node.

With 4 nodes, the slow pointer moves to the 2nd node (20), then 3rd node (30) when fast reaches the end. So the middle is 30.

🔧 Debug

advanced

Identify the error in middle element code

What error does the following code produce when trying to find the middle element of a linked list?

DSA Java

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

public class LinkedList {
    Node head;

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

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(10);
        list.head.next = new Node(20);
        list.head.next.next = new Node(30);
        System.out.println(list.findMiddle());
    }
}

A NullPointerException

B IndexOutOfBoundsException

C No error, output is 20

D Compilation error

💡 Hint

Check how fast pointer is initialized and moved.

Fast pointer starts at head.next. For 3 nodes, fast moves two steps and becomes null, but next iteration tries to access fast.next causing NullPointerException.

🧠 Conceptual

advanced

Why use two pointers to find middle?

Why does using two pointers (slow and fast) help find the middle element of a linked list efficiently?

A Because slow pointer moves twice as fast, fast pointer reaches middle first

B Because fast pointer moves twice as fast, slow pointer reaches middle when fast reaches end

C Because both pointers move at same speed, so middle is average of their positions

D Because fast pointer moves randomly, slow pointer follows it to middle

💡 Hint

Think about relative speeds of pointers.

Fast pointer moves two nodes per step, slow moves one. When fast reaches end, slow is at middle. This avoids counting nodes or extra passes.

❓ Predict Output

expert

Output after multiple middle element calls

What is the output of the following code that calls findMiddle() after removing nodes?

DSA Java

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

public class LinkedList {
    Node head;

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

    void removeFirst() {
        if (head != null) head = head.next;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);
        list.head.next.next.next.next = new Node(5);
        System.out.println(list.findMiddle());
        list.removeFirst();
        System.out.println(list.findMiddle());
        list.removeFirst();
        System.out.println(list.findMiddle());
    }
}

A

3
4
4

B

3
3
4

C

3
4
3

D

2
3
4

💡 Hint

Trace the list after each removal and find the middle.

Initially list is 1->2->3->4->5, middle is 3. After removing 1, list is 2->3->4->5, middle is 3. After removing 2, list is 3->4->5, middle is 4.

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