Delete the Middle Node of a Linked List
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ā^th 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, and5, the middle nodes are0,1,1,2, and2, respectively.
Example 1
[1] -> [3] -> [4] -> [7] -> [1] -> [2] -> [6] -> null --- [1] -> [3] -> [4] -> [1] -> [2] -> [6] -> null
Input
head = [1,3,4,7,1,2,6]Output
[1,3,4,1,2,6]Since n = 7, node 3 with value 7 is the middle node, so the list is returned after removing this node.
Example 2
[1] -> [2] -> [3] -> [4] -> null --- [1] -> [2] -> [4] -> null
Input
head = [1,2,3,4]Output
[1,2,4]For n = 4, node 2 with value 3 is the middle node, so it is removed.
Constraints
- The number of nodes in the list is in the range [1, 10^5].
- 1 <= Node.val <= 10^5