Remove Central Node from Linked List

Medium

You are given the head of a singly linked list. Your task is to eliminate the central node from the list and return the head of the modified linked list. The central node of a linked list containing n nodes is defined as the node located at position ⌊n / 2⌋ when counting from the beginning using 0-based indexing . Here, ⌊x⌋ represents the floor function, which returns the largest integer that is less than or equal to x . To clarify the central node position for various list sizes: For a list of size n = 1, the central node is at index 0 For a list of size n = 2, the central node is at index 1 For a list of size n = 3, the central node is at index 1 For a list of size n = 4, the central node is at index 2 For a list of size n = 5, the central node is at index 2 Your goal is to efficiently identify and remove this central element, then return the resulting linked list with all remaining nodes in their original order.

Example 1

Input

head = [1,3,4,7,1,2,6]

Output

[1,3,4,1,2,6]

Explanation

The linked list contains 7 nodes, so n = 7. The central node is at index ⌊7 / 2⌋ = 3, which holds the value 7. After removing this node, the resulting list is [1,3,4,1,2,6].

Example 2

Input

head = [1,2,3,4]

Output

[1,2,4]

Explanation

With n = 4 nodes, the central node is at index ⌊4 / 2⌋ = 2, containing the value 3. Removing it yields [1,2,4].

Example 3

Input

head = [2,1]

Output

[2]

Explanation

For n = 2, the central node is at index ⌊2 / 2⌋ = 1, which has value 1. After removal, only the node with value 2 remains.

Constraints

The number of nodes in the linked list is in the range [1, 10⁵].
1 ≤ Node.val ≤ 10⁵