删除链表的倒数第N个节点

题目

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

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

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

解题思路

我的思路 答案(一)
因为遍历一次，但是直到走到最后一步，不然就不知道倒数第n在哪个位置，因此就打算用一个字典，记录每一步的节点，当遍历完成以后就知道倒数n在哪里了，然后就可以在字典中找出来。当然，这样占用了O(n)的空间复杂度就高了。

别人思路 答案(二)
双指针法，求倒数问题的时候，用一个指针先往前移动n步，然后两个指针再一起往前移动直到第一个指针无法继续前进的时候，第二个指针就正好到了倒数n。(非常妙的做法！这样一来，就用只占用O(1)的空间复杂度了)

然后再利用亚节点，这样可以在遍历链表的时候，不用额外进行一些多余的判断，当然这个是因为遍历链表结构的方法造成的。遍历链表的终止条件是当前节点的下一个节点是否是None，但是这样一来，最后一个节点就无法进入遍历了，因为他的下一个节点是None，但是它本身不是None！因此设置哑节点就可以解决这个问题。

答案(一)

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        c_dict = {}
        r = head
        index = 0
        while True:
            index += 1
            c_dict[index] = r
            if r.next is not None:
                r = r.next
            else:
                break
        if n == 1:
            if index == 1:
                return None
            else:
                c_dict[index - 1].next = None
                return head
        elif n == index:
            return head.next
        else:
            c_dict[index - n].next = c_dict[index - n + 2]
            return head

答案(二)

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        fast = dummy
        slow = dummy
        for i in range(n):
            fast = fast.next
        
        while fast.next != None:
            fast = fast.next    
            slow = slow.next
            
        slow.next = slow.next.next
        return dummy.next