19_给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

1、题目
示例1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
2、代码

        def removeNthFromEnd(self, head, n):
            """
            (1)创建一个虚拟头结点 dummy,并将它指向原链表的头结点 head。
            (2)定义两个指针 fast 和 slow,初始时都指向虚拟头结点。
            (3)快指针 fast 先向前移动 n 步,即 for i in range(n+1): fast = fast.next。
            (4)同时移动快指针和慢指针,直到快指针 fast 到达链表的末尾。使用循环 while fast:,循环内部的操作为 fast = fast.next 和 slow = slow.next。
            此时,慢指针 slow 所指向的节点就是要删除的节点的前一个节点。
            (5)将慢指针 slow 所指向的节点的 next 指针指向下一个节点的 next 指针,即 slow.next = slow.next.next,实现删除倒数第 n 个节点。
            (6)返回 dummy.next,即为新链表的头结点
            """
            dummy = ListNode(0)  # 创建一个虚拟头结点,值为0
            dummy.next = head  # 将虚拟头结点指向原链表的头结点
            fast = dummy  # 快指针初始指向虚拟头结点
            slow = dummy  # 慢指针初始指向虚拟头结点
            for i in range(n + 1):  # 快指针先向前移动n步(包括虚拟头结点)
                fast = fast.next
            while fast:  # 同时移动快指针和慢指针,直到快指针到达链表末尾
                fast = fast.next  # 快指针每次移动一步
                slow = slow.next  # 慢指针每次移动一步
            slow.next = slow.next.next  # 删除倒数第n个节点,将慢指针指向的节点的next指针指向下一个节点的next指针
            return dummy.next  # 返回链表的头结点
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容