How to Solve: Find Middle of a Linked List

How to Solve: Find Middle of a Linked List

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—nail it, and you prove you can optimize traversals, handle edge cases, and think in two-pointer patterns—skills every FAANG interviewer tests."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Singly Linked List Basics – Node structure (val, next), traversal, and edge cases (empty list, single node). 2. Two-Pointer Technique – Fast and slow pointers (e.g., cycle detection in linked lists). 3. Time/Space Complexity – Big-O notation for linked list operations.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental Checklist for Every Linked List Middle Problem:

1. Clarify the Problem
2. Ask: "Should I return the first middle or second middle for even-length lists?" (e.g., [1,2,3,4] → 2 or 3?).

3. Confirm: "What should I return for an empty list or single-node list?" (e.g., None or head?).

4. Choose the Technique

5. Two-pointer (fast/slow) → Optimal (O(n) time, O(1) space).
6. Count nodes + traverse again → Brute-force (O(n) time, O(1) space, but 2 passes).

7. Recursion → Only if explicitly asked (O(n) space for call stack).

8. Initialize Pointers

9. slow = head, fast = head.

10. If using a dummy node: dummy = ListNode(0, head), then slow = fast = dummy.

11. Traverse the List

12. While fast and fast.next are not None:

    • Move slow 1 step: slow = slow.next.
    • Move fast 2 steps: fast = fast.next.next.

13. Handle Edge Cases

14. Empty list: Return None.
15. Single node: Return head.

16. Even-length list: Return slow (first middle) or slow.next (second middle).

17. Validate the Solution

18. Test with:

    • [1] → 1
    • [1,2] → 1 or 2 (depends on problem)
    • [1,2,3,4,5] → 3
    • [1,2,3,4] → 2 or 3

19. Optimize for Follow-Ups

20. If asked for second middle, adjust the loop condition or return slow.next.
21. If asked for O(1) space with recursion, explain why it’s not ideal (stack overflow risk).

? WORKED EXAMPLES

Example 1 – Basic: Find First Middle

Problem: Given a singly linked list, return the first middle node (for even length, return the left middle). Example: [1,2,3,4,5] → 3; [1,2,3,4] → 2.

Thought Process

1. Use two pointers: slow and fast.
2. Move slow 1 step, fast 2 steps per iteration.
3. When fast reaches the end, slow is at the first middle.

Solution Code (Python)

class ListNode:

    def __init__(self, val=0, next=None):

        self.val = val

        self.next = next

def middleNode(head: ListNode) -> ListNode:

    slow = fast = head

    while fast and fast.next:

        slow = slow.next

        fast = fast.next.next

    return slow

Complexity

• Time: O(n) (one pass).
• Space: O(1) (no extra space).

Why This Works

• The fast pointer moves twice as fast, so when it reaches the end, the slow pointer is at the middle.

Example 2 – Medium: Find Second Middle

Problem: Return the second middle node for even-length lists. Example: [1,2,3,4] → 3.

Thought Process

1. Adjust the loop condition to stop when fast.next is None (not fast).
2. This ensures slow lands on the second middle.

Solution Code (Python)

def middleNodeSecond(head: ListNode) -> ListNode:

    slow = fast = head

    while fast.next and fast.next.next:

        slow = slow.next

        fast = fast.next.next

    return slow.next if fast.next else slow

Complexity

• Time: O(n).
• Space: O(1).

Why This Works

• The loop stops when fast is at the last node (for even length), so slow is at the first middle. Returning slow.next gives the second middle.

Example 3 – Hard/Follow-Up: Delete Middle Node

Problem: Delete the middle node of a linked list. If the list has even length, delete the second middle. Example: [1,2,3,4] → [1,2,4].

Thought Process

1. Use two pointers to find the middle.
2. Use a third pointer (prev) to track the node before slow.
3. Delete slow by setting prev.next = slow.next.

Solution Code (Python)

def deleteMiddle(head: ListNode) -> ListNode:

    if not head or not head.next:

        return None


    slow = fast = head

    prev = None


    while fast and fast.next:

        prev = slow

        slow = slow.next

        fast = fast.next.next


    prev.next = slow.next  # Delete the middle node

    return head

Complexity

• Time: O(n).
• Space: O(1).

Why This Works

• prev tracks the node before slow, allowing us to bypass slow and delete it.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. To find the middle of a linked list:

1. Clarify: Ask if you need the first or second middle for even-length lists.
2. Two-pointers: Initialize slow and fast at the head. Move slow 1 step, fast 2 steps per iteration.
3. Loop condition: While fast and fast.next are not None, keep moving.
4. Edge cases: Handle empty lists and single-node lists upfront.
5. Follow-ups: For deletion, track the node before slow with a prev pointer.

This pattern is a classic—it’s O(n) time, O(1) space, and shows you can optimize traversals. Practice it until it’s muscle memory. You’ve got this!

? Final Notes

• Practice Variations: Try finding the middle of a doubly linked list or a circular linked list.
• Whiteboard Tip: Draw the list and pointers as you code. Interviewers love visuals.
• Time Yourself: Aim to solve this in under 10 minutes in an interview.

Now go crush that interview! ?