LC2095 Delete the Middle Node of a Linked List 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

Fast & Slow — find the middle car in one pass, then unlink it.

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋ᵗʰ node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

- For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1

Input:: head = [1,3,4,7,1,2,6]
Output:: [1,3,4,1,2,6]
Explanation:: Explanation:
The figure above represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.

Example 2

Input:: head = [1,2,3,4]
Output:: [1,2,4]
Explanation:: Explanation:
The figure above represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3

Input:: head = [2,1]
Output:: [2]
Explanation:: Explanation:
The figure above represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Constraints (ข้อจำกัด)

The number of nodes in the list is in the range [1, 10^5].
1 <= Node.val <= 10^5

Full solution · Try yourself firstพับไว้ด้านใน — คลิกเมื่อพร้อมดู

This matches the section signal: "Two-speed walk (Fast & Slow Pointers)" — find the middle car, then unlink it.

1. Mindset Shift

The naive way is one pass to count n, then a second pass to stop at ⌊n/2⌋ and unlink — correct, but two traversals.

Key insight: Fast & Slow — slow moves 1, fast moves 2. When fast reaches the end, slow sits on the middle. One pass!

Knowing the middle isn’t enough to delete — you need prev (the node before) so you can do prev.next = slow.next and skip the middle.

2. The Logic — 4 Steps

Open three pointers, then walk until fast runs out:

Edge case — if the list has one node (head.next is None), deleting it leaves empty → return None
Prep pointers — prev = None · slow = head · fast = head
Walk together — while fast and fast.next: prev = slow, then slow += 1, fast += 2
Unlink — prev.next = slow.next, then return head

3. LeetCode-Ready Code

Short and straightforward:

Submit this on LeetCodepython

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Step 1: single node → empty list
        if head.next is None:
            return None

        prev = None                 # node before the middle
        slow = head                 # moves 1 → ends on middle
        fast = head                 # moves 2

        # Step 3: walk until fast runs out
        while fast and fast.next:
            prev = slow
            slow = slow.next        # slow +1
            fast = fast.next.next   # fast +2

        # Step 4: skip the middle
        prev.next = slow.next
        return head

4. Dry Run — 1 → 3 → 4 → 7 → 1 → 2 → 6

Step	prev (val)	slow (val)	fast (val)	Note	list now
Before loop	None	1	1	fast.next exists → enter loop	1 → 3 → 4 → 7 → 1 → 2 → 6
Round 1	1	3	4	fast.next exists	1 \| 3 → 4 → 7 → 1 → 2 → 6
Round 2	3	4	1	fast.next exists	1 → 3 \| 4 → 7 → 1 → 2 → 6
Round 3	4	7	6	fast.next gone → stop	1 → 3 → 4 \| 7 → 1 → 2 → 6
After loop	4	7 (middle)	6	Unlink: 4.next → 1 (skip 7)	1 → 3 → 4 → 1 → 2 → 6

The | mark splits two pieces: left = up through prev · right = slow as head (the node to delete is at the right head) — final train [1, 3, 4, 1, 2, 6]

5. Edge Cases & Pitfalls

The "single node" case — if you skip the guard:

The loop never runs (fast.next is None from the start)
prev is still None → prev.next crashes (AttributeError)

while condition

Write while fast and fast.next — if you only write while fast, fast.next.next blows up when fast lands past the end on None.

6. Time & Space Complexity

Time O(n) — one pass through the list
Space O(1) — a few pointers, no new list

💡 Pattern summary

Fast & Slow finds the middle in one pass, and deleting/editing a linked-list node always needs a pointer to the previous node — both ideas show up again and again.