题目

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

示例

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

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

说明：给定的 n 保证是有效的。

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

解答

方案1：走两趟

1. 首先从头到尾遍历链表，统计输入链表的长度list_len；
2. 计算要删除的节点位置，处理特殊情况，如输入节点为空，要删除的节点位置为0或负数等；
3. 把删除倒数第N个节点转变成删除正数第list_len-N个节点的问题，从头到尾遍历链表，并删除指定位置元素；

我们这里删除链表使用语句node.next = node.next.next即可删除原先node.next位置的元素，代码如下：

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        解决思路：走两趟
        :param head:
        :param n:
        :return:
        """

        def get_len(head):      # 获取一个链表的长度
            n = 0
            while head:
                n += 1
                head = head.next
            return n

        list_len = get_len(head)
        if list_len == 0:                           # 输入是个空链表
            return

        node_to_delete = list_len - n               # 要删除的节点的位置
        if node_to_delete == 0:
            return head.next

        elif node_to_delete < 0:
            return head

        else:

            # 将倒数第n个转换为正数第cur_len - n个。
            i = 0
            cur_node = head
            while cur_node:
                if i == node_to_delete - 1:             # 遇到了要删除的结点的前一个结点
                    cur_node.next = cur_node.next.next  # 删除要删除的结点
                else:
                    cur_node = cur_node.next            # 当前指针后移
                i += 1

            return head                                 # 返回链表头结点

执行用时 : 56 ms, 在Remove Nth Node From End of List的Python3提交中击败了80.63% 的用户
内存消耗 : 13 MB, 在Remove Nth Node From End of List的Python3提交中击败了93.66% 的用户

（其实这个性能波动有时挺大）

方案2：快慢指针

我们定义两个指针，快指针和慢指针，让快指针先于慢指针走N步，然后两指针同步向后走，当快指针遍历到链表末尾时，删除慢指针后的元素即可。

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        解决思路：双指针法
        :param head:
        :param n:
        :return:
        """

        pre_head = ListNode(0)          # 定义一个临时节点
        pre_head.next = head            # 将链表挂在临时节点上，临时节点成为头节点
        slw = fst = pre_head            # 快慢指针开始位置都是临时节点

        i = 0
        while i <= n and fst:           # 快指针提前走n+1步，走到原链表第n个位置
            fst = fst.next
            i += 1

        while fst:                      # 快慢指针同时走，直到快指针走到链表末尾
            fst = fst.next
            slw = slw.next

        slw.next = slw.next.next        # 把慢指针的下一个节点（倒数第n个节点）删除
        return pre_head.next

如有疑问或建议，欢迎评论区留言~