19. 删除链表的倒数第N个节点 [medium]

19. 删除链表的倒数第N个节点 [medium]

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

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

示例：

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

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

说明：

• 给定的 n 保证是有效的。

进阶：

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

通过次数191,668 | 提交次数492,349

Second Try

2020-07-07

看了题解才知道还有双指针法，双指针法在链表里算是常见的技巧了，没接触过很难想到，接触了就会觉得巧妙。

倒数n个元素，谁能想到开两个起点指针，其中一个先走个n步，然后两个指针再一起走（注意这时候两个指针之间间隔为n），第一个到达结尾的时候，上一个指针刚好在倒数n + 1的位置。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(None)
        dummy.next = head 
        first = second = dummy 
        c = 0
        while first.next and c < n:
            first = first.next 
            c += 1
        while first.next:
            second = second.next 
            first = first.next
        second.next = second.next.next 
        return dummy.next  

• 执行用时：16 ms, 在所有 Python 提交中击败了97.40%的用户
• 内存消耗：12.7 MB, 在所有 Python 提交中击败了9.09%的用户

First Try

2020-07-06

一波扫描，那就得牺牲一些空间来缓存吧。

另外有两个特殊条件需要考虑，一是整体被删没了，二是head也被删没了。

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        # 写第一波的时候，又没考虑好边界条件: [1] 1
        reserve = [head]  # n + 1
        node = head
        while node.next:
            node = node.next
            reserve.append(node)
            if len(reserve) > n + 1:
                reserve.pop(0)

        # 全删没了
        if n == 1 and len(reserve) == 1:
                return None
        # 前面删没了
        if len(reserve) == n:
            return reserve[1]
        # 正常部分, len(reserve) = n + 1
        reserve[0].next = reserve[1].next
        return head

• 执行用时：28 ms, 在所有 Python 提交中击败了47.51%的用户
• 内存消耗：12.8 MB, 在所有 Python 提交中击败了9.09%的用户