19. 删除链表的倒数第 N 个结点

Difficulty
Medium
Tags
链表
URL
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
Star
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
notion imagenotion image
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz
通过次数545,957提交次数1,268,717
 

题目进阶

若要删除位于 a/b 处节点。
首先根据链表长度计算需要删除的节点位置：
如果链表长度为n，那么需要删除第 math.ceil(n * a / b) 个节点。
知道了要删除哪个节点后，只需要找到前一个节点即可。

法1 双指针

思路
采用前后双指针，让前指针先往前走n步，然后后指针再跟着走，直到前指针到最后一个节点。
因为是要删除倒数第n个节点，所以second节点要指向倒数第n+1个节点。
题解
# 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: ListNode, n: int) -> ListNode:
        if head is None:
            return head
        dummy = ListNode(0, head)
        first, second = dummy, dummy
        while n > 0 and first:
            first = first.next
            n -= 1
        # 如果长度不够 n
        if first is None:
            return None

        while first.next:
            first = first.next
            second = second.next

        second.next = second.next.next

        return dummy.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: ListNode, n: int) -> ListNode:
        if head is None:
            return head

        dummy = ListNode(-1, head)
        fst, scd = dummy, dummy

        # 此处的 n 顺便可以统计节点个数
        while fst.next:
            fst = fst.next
            n -= 1
            if n <= -1:
                scd = scd.next
        # 如果 n == 0 说明删除的是第一个节点
        if n > 0:
            return head

        scd.next = scd.next.next
        return dummy.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: ListNode, n: int) -> ListNode:
        dummy = ListNode(-1, head)
        f, s = dummy, dummy
        
        while f:
            f = f.next
            n -= 1
            if n < -1:
                s = s.next
        # 表示 没有节点需要删除
        if n >= 0:
            return dummy.next
        # 删除节点
        s.next = s.next.next
        return dummy.next