Delete the Middle Node

New·#2095·Medium·Linked List

Stop slow pointer one node before the middle and skip the middle node

Asked at:AmazonMicrosoftAdobe

Practice mode

Step

Initialization

slow set to 1, fast set to 3.

Cache workspace

Tortoise and Hare Variation

Step 1 / 6init

100%

list

slow

→

fast

→

→null

slow val =

fast val =

Explanation

Initialize slow at head (index 0) and fast at head.next.next (index 2). This offsets the pointers so slow stops exactly one node BEFORE the middle.

step 1 / 6

Space play← → stepHome reset

TimeO(n)·SpaceO(1)

Tortoise and Hare Variation

1class Solution {
2    deleteMiddle(head) {
3        if (head === null || head.next === null) {
4            return null;
5        }
6 
7        let slow = head;
8        let fast = head.next.next;
9 
10        while (fast !== null && fast.next !== null) {
11            slow = slow.next;
12            fast = fast.next.next;
13        }
14 
15        // Deletes the middle node
16        slow.next = slow.next.next;
17        return head;//slow: 1fast: 3
18    }
19}

slow1

fast3

Command Palette

Delete the Middle Node

Delete the Middle Node