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

难度：Medium.

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

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

解析：
这里的相关标签是：链表，双指针.

这道题有2种解法：两次遍历算法，一次遍历算法。

• 两次遍历算法：相当于把元链表分为两部分，倒数第n个节点前的链表 和 倒数第n个节点后的链表；并把他们连接在一起。

• 一次遍历算法：相当于把两次遍历算法优化了，不需要两次遍历，而是用两个指针（双指针）来完成。对于指针p1, p2，指针p1在前，指针p2在后。保证指针p1, p2之间始终相差个node，那么当指针p1指向最后的None时，指针p2刚好指向倒数第N个node。重新连接指针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
        """
        dummy = ListNode(0)
        dummy.next = head
        
        p1 = p2 = dummy
        
        for i in range(n):
            p1 = p1.next
            
        while p1.next:
            p1 = p1.next
            p2 = p2.next
            
        p2.next = p2.next.next
        
        return dummy.next