leetcode-19

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

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

思路1（计算链表长度）：

1. 先依次将元素保存到list中，获得链表长度
2. 先检查是不是要删除头结点，如果是直接head=head.next
3. 通过遍历list，进行相应的元素删除

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p = head
        stack = [-1 for i in range(101)] # 使用列表模拟一个栈
        count = 0 # 计数

        while p:
            stack[count] = p.val
            p = p.next
            count += 1

        if count-n == 0: # 找到要删除的元素，是第一个元素
                head = head.next 
                return head
        p = head
        pre = p
        for i in range(0,count):
            if count - n == i: # 找到删除的元素
                # print(i,p.val,pre.val)
                pre.next = p.next
                return head
            else:
                pre = p # 保存当前的地址
                p = p.next # p指向下一个地址
                
        return head

官方题解2（栈）：

入栈后弹出n个，栈顶元素即为要删除元素的前驱结点

def removeNthFromEnd2(self, head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0,head) # 添加头结点

    stack = list()
    cur = dummy

    while cur:
        stack.append(cur)
        cur = cur.next # 迭代至最后一个节点
    
    for i in range(n):
        stack.pop() # 弹出元素

    prev = stack[-1] # 获取栈顶元素，它是被删除元素的前一个元素
    prev.next = prev.next.next
    return dummy.next 

官方题解3（快慢指针）：

先快指针遍历n次，再让慢指针出发遍历。让快指针指向头结点，慢指针指向哑结点，这样可以保证，当first指针到末尾的时候，second指针能正好处于倒数第n个节点前一个。

def removeNthFromEnd3(self, head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0,head) # 添加头结点
        
    first = head # 快指针
    second = dummy # 慢指针

    count = 0
    while first:
        first = first.next
        if count == n:
        second = second.next
            
        if count < n:
           count += 1
        
     second.next = second.next.next
     print('--',second.val)
     return dummy.next