LeetCode 19. 删除链表的倒数第N个节点 Remove Nth Node From End of List
Table of Contents
一、中文版
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
二、英文版
Given a linked list, remove the n-th node from the end of list and return its head. Example: Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
三、My answer
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: Node = ListNode(None) Node.next = head slow = Node fast = Node for i in range(n): fast = fast.next while fast.next != None: fast = fast.next slow = slow.next slow.next = slow.next.next return Node.next """ 如果不设置哨兵节点的话，下述情况会报错： Line 13: AttributeError: 'NoneType' object has no attribute 'next' [1] 1 """
四、解题报告
使用快慢指针算法可以只遍历一遍链表完成题目。
在头结点之前设置一个哨兵节点 Node，Node 指向 head 头结点。
1、快慢指针都指向 Node 节点
2、快指针先走 n 步，也就是要删除的倒数第 n 个节点的 n
3、快慢指针同时前进，直到快指针的下一个节点为空，此时慢指针指向的就是要删除的节点的前一个节点，使用
slow.next = slow.next.next 就可删除慢指针指向节点的下一个节点。
