删除链表的中间节点

难度: Medium

给你一个链表的头节点 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⁵

Submission

运行时间: 1308 ms

内存: 56.8 MB

# 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]:
        if head.next is None:
            return None
        f = s = head
        pre = ListNode(next=head)
        while f and f.next:
            f = f.next.next
            s = s.next
            pre = pre.next
        pre.next = pre.next.next
        return head

Explain

这个题解使用了快慢指针的方法来查找链表的中间节点。快指针`f`每次移动两步，慢指针`s`每次移动一步。通过这种方式，当快指针到达链表末尾时，慢指针正好位于链表的中间位置。为了能够删除中间节点，我们使用一个额外的指针`pre`，始终指向慢指针的前一个节点，这样我们可以轻松地跳过中间节点，从而实现删除操作。如果链表只有一个节点，直接返回`None`。

时间复杂度: O(n)

空间复杂度: O(1)

# 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]:
        if head.next is None:
            return None  # 如果链表只有一个节点，删除后返回None
        f = s = head
        pre = ListNode(next=head)  # 创建一个dummy节点，其next指向head，以便处理头节点的删除
        while f and f.next:
            f = f.next.next  # 快指针每次移动两步
            s = s.next  # 慢指针每次移动一步
            pre = pre.next  # pre指针跟随慢指针，始终保持在慢指针的前一个节点
        pre.next = pre.next.next  # 删除中间节点
        return head  # 返回修改后的头节点

Explore

在找到中间节点后，可以通过`pre.next = pre.next.next`来删除节点，这是因为`pre`指针指向待删除节点的前一个节点，通过修改`pre`的`next`指向，即可将中间节点从链表中断开，链接到中间节点之后的节点。这种操作不会影响链表的完整性，因为所有节点仍然通过链接相连，只是移除了中间的一个节点。

当链表长度为偶数时，慢指针`s`停止的位置是两个中间节点中的第一个。这是因为当快指针`f`到达链表末尾时（`f.next`为`None`），慢指针`s`将位于前半部分的最后一个节点。因此，在偶数长度的链表中，若定义中间节点为两个中间节点中的第二个，慢指针实际上停在了偏向前一个。

对于只有两个节点的链表，根据题解中的逻辑，快指针`f`会在第二个节点处停止（因为`f.next.next`为`None`），这时慢指针`s`和`pre`都停在第一个节点。执行`pre.next = pre.next.next`（即`pre.next = s.next`）将删除第二个节点。因此，链表将只剩下第一个节点，即删除中间节点后，返回的结果为只含有第一个节点的链表。

快指针`f`在遍历时使用`f.next.next`确保每次前进两步。在链表节点数为奇数和偶数时，快指针的行为略有不同：对于奇数节点，快指针最终会停在最后一个节点（`f.next`为`None`）；对于偶数节点，快指针会停在倒数第二个节点（`f.next.next`为`None`）。为确保不会出现访问空指针错误，代码中应在访问`f.next.next`之前检查`f`和`f.next`是否为`None`。这种检查在题解中已经实现，确保了代码在遍历过程中不会引发空指针异常。