2025/7/24

题目（meidum)：

---

我的思路

因为要删除指定位置的节点，所以我们知道要获取当前删除位置节点的前驱节点（不过注意头节点没有前驱节点，所以如果删除位置是头结点需要特殊处理）。然后它又说是倒数第n个节点，也就是反着数到的节点位置，那我就想到了之前做回文链表的时候用到的递归的思想，可以倒着遍历链表。

所以就是：

①遍历到节点的末尾

②每次一层递归返回的值是这一层所在的节点

③每一次层递归完成都会让n - 1，当n == 0的时候说明这个位置的节点的下一个节点是需要被删除的

④在最后递归结束的时候，如果发现n >= 0，那就说明要删除的节点的头结点，直接返回头结点的next节点即可

代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head.next == None:
            return None

        #递归处理
        self.n = n
        def visitNode (curNode = head,) -> Optional[ListNode]:
            #只要不为空就可以进入第一层递归
            if curNode != None:
                #lastNode作为当前节点的后一个节点存在
                self.lastNode = visitNode(curNode.next)
                #当n变成0的时候，就说明当前节点的下一个节点就是要删除的节点了
                if self.n == 0: 
                    curNode.next = self.lastNode.next if self.lastNode else None
                elif self.n < 0 :
                    return curNode
                #每次一层递归调用结束n就减少1
                self.n -= 1

            #每次一层递归结束的时候返回这一层所在的节点给下一层获取
            return curNode       

        visitNode()

        #如果递归出来发现n >= 0 ，那只能说明要删除的节点是正数第一个
        return head if self.n < 0 else head.next

时间复杂度：O（N）

空间复杂度：O（N）

---

优化思路：

我们递归主要是为了倒着遍历，但是这样递归遍历的可读性说实话稍微有点差。而且递归的时候也没有其他特别的数据需要处理，就只是当前节点和下一个节点而已。那我们直接用栈来处理这个链表不就好了？而且我们可以考虑先给它一个自定义头结点，这样就不用再对要删除的节点是第一个节点进行特殊的处理了

①声明一个头结点连接在链表开头

②声明一个栈并遍历链表以压入节点

③根据n的大小去弹出栈中对应数量的节点

④最后把当前栈顶元素连接到最后一个弹出的节点的下一个节点即可

代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head.next == None:
            return None

        #自定义头结点连接
        dummy = ListNode(0, head)
        stack = list()
        p = dummy

        #遍历压入栈
        while p :
            stack.append(p)
            p = p.next

        #根据n弹出栈
        deletNode = None
        for i in range(n):
            deletNode = stack.pop()

        #栈顶元素连接到删除元素的下一个
        stack[-1].next = deletNode.next

        #返回自定义头结点的下一个节点即可
        return dummy.next

时间复杂度：O（N）

空间复杂度：O（N）

是不是比那啥递归直观简单多了

---

其他思路：

1.计算正序位置

就是先遍历一遍链表计算链表的长度，然后由此计算出正序遍历的时候删除节点是第几个，从而再遍历一遍得到要删除节点的前一个结点进行删除操作。这里同样可以添加自定义结点

比较简单，代码就不写了（偷懒）

时间复杂度：O（N）

空间复杂度：O（1）  【省空间又简单了】

2.双指针

也可以用双指针的方式来解决这个问题。倒数第n个是指什么，是不是指从这个结点到要末尾结点的距离+1。也就是说，如果我们一开始就用一个前指针，一个后指针保持好这个n的距离，那当后指针指向None的时候，前指针正好就在要删除的结点位置处。那我们再搭配上自定义头结点，让前指针从自定义头结点开始，那到达的时候正好就是要删除的结点的前驱结点了。

总之就是：

①声明自定义头结点dummy并指向head

②定义两个指针slow和fast，slow指向dummy，fast指向head

③让fast先拉开距离n

④让fast和slow同步遍历链表，直到fast为None

⑤进行删除节点操作

代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head.next == None:
            return None

        #自定义头结点连接
        dummy = ListNode(0, head)
        slow, fast = dummy, head

        #让fast指针和slow指针保持一定的距离
        for i in range(n):
            fast = fast.next

        #当fast指针为空的时候，slow指针正好在要删除的结点的前驱结点处
        while fast:
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next
        return dummy.next

时间复杂度：O（N）

空间复杂度：O（1）

挺巧妙的对吧

---

总结：

①对于链表而言，目前常用的方法有正向普通遍历、递归遍历、快慢指针遍历、同距离双指针遍历来解决问题

②对于递归来说，它往往可以转化成更直观的栈的形式

③倒数第几个其实是指这个结点和末尾结点的距离的