19. 删除链表的倒数第N个节点(Medium)

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

样例

Input: 1->2->3->4->5, n = 2
Ouput: 1->2->3->5

题解

本题和 剑指Offer.链表中倒数第k个节点 很像，只是一个是返回，一个是删除。

删除的话，就需要使用到 伪节点(dummpyHead) ，因为可能连Head节点都删了，加上伪节点可以更方便。

使用双指针

首先让 p1 走 n 步，然后让 p2 指向 dummpHead，这样 p2 和 p1 相差 n+1 个单位。当 p1 走到尽头的时候，p2 正好位于 倒数第n 个元素的前方，正好直接删除 p2.next = p2.next.next

递归实现

递归可以在回退的时候，计算层信息。

Python示例

使用双指针

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummpyHead = ListNode(None)
        dummpyHead.next = head 
        p1 = head 
        for _ in range(n):
            p1 = p1.next 
        p2 = dummpyHead
        while p1:
            p1 = p1.next 
            p2 = p2.next 
        p2.next = p2.next.next 

        return dummpyHead.next
      
# 思路一样，实现稍微有点不同
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummpyHead = ListNode(None)
        dummpyHead.next = head 
        p1 = dummpyHead 
        p2 = dummpyHead 
        for _ in range(n):
            p1 = p1.next 
        while p1.next:
            p1 = p1.next 
            p2 = p2.next 
        p2.next = p2.next.next 

        return dummpyHead.next 

递归实现

class Solution:
    level = 0 
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def recur(head, n):
            if not head:
                return 
            dfs(head.next, n)
            self.level = self.level + 1 # 从尾节点计算
            if self.level == n + 1: # n + 1层是 倒数n节点的前一个节点
                head.next = head.next.next # 删除
            return head 
        
        dummpyHead = ListNode(None) # 伪节点
        dummpyHead.next = head 

        recur(dummpyHead, n) # 递归解决
        return dummpyHead.next