LeetCode 19. 删除链表的倒数第N个节点（Remove

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

题目

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

示例：

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

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

给定的 n 保证是有效的。

进阶：

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

知识点

解题

1. 只遍历一遍就可以知道倒数第n个数据的值。
2. 直观的想法是：先遍历一遍知道总数量m，然后再走一遍，走m-n步就走到了要删除节点的前一个节点删除即可。
3. 更好点的做法：使用两个指针p1,p2，p1先走n步，然后一起走，当p1走到最后的节点（p1->next is None），p2恰好走到要删除节点的前一个.

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
        """
        h1 = head
        h2 = head

        for i in range(n):
            h1 = h1.next

        while h1.next is not None:
            h1 = h1.next
            h2 = h2.next

        h2.next = h2.next.next
        return head

4. 这种解法的bug：如果是删掉链表的第一个数，那p1要先走n步，最终为h1=None，此时h1.next就会出错。
5. 而且删掉首节点，也不能通过h2.next = h2.next.next实现。
6. 可以在此情况下在头部加入哑节点或者直接返回head.next

    if h1 is None:
        return head.next

7. 加入哑节点的方法：<u>p1先走n+1步，当p1走到None的时候</u>，p2走到了被删节点的前一个节点，删除节点后，返回哑节点的下一个节点

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        h = ListNode(0)
        h.next = head

        h1 = h
        h2 = h

        for i in range(n + 1):
            h1 = h1.next
        
        while h1 is not None:
            h1 = h1.next
            h2 = h2.next

        h2.next = h2.next.next
        return h.next