Cut Out the Middle

Medium

You get the head head of a singly linked list with n nodes. Remove its middle node and return the head of the resulting list. The middle node is the one at 0-based index n // 2. For example, for n = 1, 2, 3, 4, 5 that is index 0, 1, 1, 2, 2 respectively. Try to do it in a single pass over the list.

Example 1

head=list_node([6, 2, 9, 4, 1]) → [6, 2, 4, 1]

The list has 5 nodes, so the middle one is at index 5 // 2 = 2, the value 9.

Example 2

head=list_node([3, 8, 5, 7]) → [3, 8, 7]

With 4 nodes, the middle is index 4 // 2 = 2, the value 5.

Example 3

head=list_node([11]) → None

The only node is the middle one; removing it leaves an empty list.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ node value ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Linked List Two Pointers

Similar problems

Drop the K-th Node From the Tail Medium Move the Tail to the Front Medium Sorted List, Unique Values Only Medium Split a List Around a Pivot Medium List Folded From Both Ends Medium

Input

head=list_node([6, 2, 9, 4, 1])

Expected

[6, 2, 4, 1]

Run checks the first 3 tests in your browser. Submit checks all 57 tests on the server, hidden ones included.