删除链表 M 个节点之后的 N 个节点

Submission

运行时间: 39 ms

内存: 17.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 deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
        pre = head
        while pre:
            for _ in range(m - 1):
                if pre:
                    pre = pre.next
            if pre is None:
                return head
            cur = pre
            for _ in range(n):
                if cur: 
                    cur = cur.next
            pre.next = None if cur is None else cur.next
            pre = pre.next
        return head

Explain

此题解的思路是使用两个指针来遍历链表。首先，使用指针pre沿着链表移动m个节点，这些节点不需要删除，是保留的。接着，pre停在第m个节点上，此时使用另一个指针cur从pre的位置开始，继续向前移动n个节点，这n个节点是需要被删除的。最后将pre的next指针指向cur的下一个节点，这样就跳过了中间需要删除的n个节点。重复这个过程直到链表结尾。

时间复杂度: 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 deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
        pre = head  # 初始指向链表头部
        while pre:  # 遍历链表直到末尾
            for _ in range(m - 1):  # 移动m-1次，因为pre已经在第一个节点上
                if pre:
                    pre = pre.next  # 移动到保留的最后一个节点
            if pre is None:  # 如果移动过程中链表结束，返回head
                return head
            cur = pre  # cur从pre开始，用于跳过n个需要删除的节点
            for _ in range(n):  # 移动n次
                if cur: 
                    cur = cur.next  # 移动到要删除的最后一个节点
            pre.next = None if cur is None else cur.next  # 跳过n个节点，直接链接到下一个保留的节点
            pre = pre.next  # 继续下一轮m+n节点的处理
        return head  # 返回修改后的链表头部

Explore

在此题解中，`for _ in range(m - 1)`是用来确保`pre`指针移动到要保留节的最后一个节点上。因为`pre`一开始已经指向链表的头部，即已经处于第一个保留节点上。所以，我们只需要额外移动`m-1`次来让`pre`停留在第`m`个节点上，即保留节的最后一个节点。如果使用`for _ in range(m)`，`pre`将会指向第`m+1`个节点，即过度移动了一个位置。

当链表长度小于m时，`pre`指针确实有可能在尝试移动`m-1`次时变成`None`，这意味着没有足够的节点可以保留。在这种情况下，已经完成了可能的节点保留操作，没有剩余节点需要删除。因此，直接返回原始链表头`head`是合适的，因为实际上没有删除任何节点，保持了链表的完整性。

如果链表的节点数不足以进行完整的n次删除，`cur`指针会在移动过程中变成`None`。删除操作是通过设置`pre.next`指向`cur.next`来完成的。当`cur`变为`None`时，这表示后续没有更多节点可以删除，因此`pre.next`会被设置为`None`。这样处理实际上是将`pre`之后的所有节点都删除了，即使它们的数量少于n。

在设置`pre.next`指向`cur.next`后，`pre`指针需要更新指向`cur.next`，以便继续下一轮的处理。`cur`指针本身在这个过程中已经完成了它的任务，即确定了删除节点的范围。一旦完成这个连接，`cur`指针不需要重新定位。接下来，只需移动`pre`指针到新的位置即可继续执行下一个周期的节点保留与删除。