【LeetCode】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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

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

#链表存入数列中随机访问

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        arr = []
        length = 0
        new = ListNode(0,head)#构造一个带头结点的链表
        tmp = new
        while tmp:
            arr.append(tmp)
            tmp = tmp.next
            length += 1
        arr[length-n-1].next = arr[length-n-1].next.next
        return new.next

#入栈

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        arr = []

        new = ListNode(0,head)
        tmp = new
        while tmp:
            arr.append(tmp)
            tmp = tmp.next
        
        for i in range(n):
            arr.pop()
        pre = arr.pop()
        pre.next = pre.next.next
        return new.next

#双指针。进阶：一趟扫描
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        new = ListNode(0,head)
        first = new
        second = head#即new.next
        for i in range(n):
            second = second.next
        
        while second:
            first = first.next
            second = second.next
            
        first.next = first.next.next
        return new.next