How do I identify the middle node in a linked list using pointers?

Use a fast pointer moving two steps and a slow pointer moving one step. When the fast pointer reaches the end, the slow pointer points to the middle node.

What happens if the linked list has only one node?

If the list has one node, removing the middle node results in an empty list, so you should return null.

How do I handle even-length linked lists for middle node deletion?

For an even-length list, remove the lower middle node at index ⌊n / 2⌋ using the same fast-slow pointer approach.

Can this method be done in one pass?

Yes, using the fast and slow pointer technique allows locating and deleting the middle node in a single traversal.

Does deleting the middle node require extra space?

No, this approach only uses a few pointers for traversal and deletion, resulting in O(1) space complexity.

#2095

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

删除链表的中间节点

给你一个链表的头节点 head 。删除链表的中间节点，并返回修改后的链表的头节点 head 。长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。对于 n = 1 、 2 、 3 、 4 和 5 的情况，中间节…

链表双指针

题目描述

给你一个链表的头节点 head 。删除链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

示例 1：

输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。

示例 2：

输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。

示例 3：

输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

提示：

链表中节点的数目在范围 [1, 10⁵] 内
1 <= Node.val <= 10⁵

lightbulb

解题思路

方法一：快慢指针

快慢指针法是一种用于解决链表中的问题的常用技巧。我们可以维护两个指针，一个慢指针 $\textit{slow}$ 和一个快指针 $\textit{fast}$ 。初始时 $\textit{slow}$ 指向一个虚拟节点，该虚拟节点的 $\textit{next}$ 指针指向链表的头节点 $\textit{head}$ ，而 $\textit{fast}$ 指向链表的头节点 $\textit{head}$ 。

然后，我们每次将慢指针向后移动一个位置，将快指针向后移动两个位置，直到快指针到达链表的末尾。此时，慢指针指向的节点的下一个节点就是链表的中间节点。我们将慢指针指向的节点的 $\textit{next}$ 指针指向下下个节点，即可删除中间节点。

时间复杂度 $O(n)$ ，其中 $n$ 是链表的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        slow, fast = dummy, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        slow.next = slow.next.next
        return dummy.next

speed

复杂度分析

指标	值
时间	complexity is O(n) because each node is visited at most once with the fast and slow pointer traversal. Space complexity is O(1) as no extra data structures are used, only a few pointers for traversal and deletion.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting an optimal single-pass solution using two-pointer technique.
question_mark
Looking for correct pointer updates without breaking the list structure.
question_mark
Interest in handling edge cases like one or two nodes correctly.

warning

常见陷阱

外企场景

error
Not updating the previous node's next pointer correctly, leaving the middle node in place.
error
Assuming the list length is known or using extra space unnecessarily.
error
Misidentifying the middle node in even-length lists by picking the higher index.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Delete the nth node from the end using a similar fast-slow pointer approach.
arrow_right_alt
Remove multiple nodes at regular intervals using pointer manipulation patterns.
arrow_right_alt
Delete the middle node in a circular linked list while maintaining the loop.

help

常见问题

外企场景

继续练习

#2130 链表最大孪生和 #1721 交换链表中的节点 #2105 给植物浇水 II