Description
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:
|
|
Example 2:
|
|
Example 3:
|
|
Constraints:
- The number of nodes in the list is in the range
[1, 105]
. 1 <= Node.val <= 105
Solutions
Fast and Slow Pointer Approach: Use two pointers, fast
and slow
, to traverse the linked list. The fast pointer moves two steps at a time, while the slow pointer moves one step at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle of the list.
Note: If the linked list has only one node, we remove this node and return an empty list. However, since this node does not have a previous node, current
is meaningless. Therefore, we can make a special check before traversal and directly return a null pointer as the answer.
|
|
Why does the slow pointer end up at the midpoint?
Let the length of the linked list be ( n ) (with node indices starting from 0, where the head node has index 0). The slow pointer moves at a speed of 1 node per step, while the fast pointer moves at a speed of 2 nodes per step. After ( k ) iterations (i.e., after the slow pointer has moved ( k ) steps), the slow pointer is at index ( k ), and the fast pointer is at index ( 2k ).