【链表】Leecode-19. 删除链表的倒数第 N 个结点

【题目】

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

【题解】

题解1：

• 思路

         删除节点是将该节点的前一个节点指向该节点的后一个节点，该节点可能是头节点，所以需要加一个头的伪节点

         两个指针，fast指针先走n+1步，然后slow指针和fast指针一起走，当fast指针走完那么slow指针就是到达倒数第n个节点，slow的next指向next.next，即为删除

• 复杂度

         时间复杂度：O(n)，空间复杂度：O(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: Optional[ListNode], n: int) -> Optional[ListNode]:
        pre = ListNode(0, head)
        fast = pre
        slow = pre
        index = 0
        while index<n+1:
            fast = fast.next
            index+=1
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return pre.next