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

题目

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。

进阶：
你能尝试使用一趟扫描实现吗？

代码

一趟扫描实现：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def removeNthFromEnd(head, n):
    """一趟扫描实现"""
    sentinel = ListNode(None)   # 哨兵节点，即链表第一个元素之前的空节点
    sentinel.next = head

    delete_node = sentinel      # 要删除的节点
    pre_node = ListNode(None)   # 要删除节点的前一个节点

    # 扫描链表
    while head is not None:
        n = n - 1               # 计数
        if n <= 0:              # head遍历到第n个元素，则开始移动delet_node
            pre_node = delete_node
            delete_node = delete_node.next
            # print(pre_node.val)
            # print(delete_node.val)
        head = head.next

    pre_node.next = pre_node.next.next    # 删除节点

    return sentinel.next


if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]
    sentinel = ListNode(None)   # 哨兵节点
    pre_node = sentinel

    for idx in range(len(nums)):
        node = ListNode(nums[idx])
        pre_node.next = node
        pre_node = pre_node.next

    cur_node = sentinel.next
    while cur_node is not None:
        print(cur_node.val)
        cur_node = cur_node.next

    n = 2
    head = removeNthFromEnd(sentinel.next, n)

    while head is not None:
        print(head.val)
        head = head.next