難度：Medium.

給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。

示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.

解析：
這里的相關(guān)標簽是：鏈表，雙指針.

這道題有2種解法：兩次遍歷算法，一次遍歷算法。

• 兩次遍歷算法：相當于把元鏈表分為兩部分，倒數(shù)第n個節(jié)點前的鏈表 和 倒數(shù)第n個節(jié)點后的鏈表；并把他們連接在一起。

• 一次遍歷算法：相當于把兩次遍歷算法優(yōu)化了，不需要兩次遍歷，而是用兩個指針（雙指針）來完成。對于指針p1, p2，指針p1在前，指針p2在后。保證指針p1, p2之間始終相差個node，那么當指針p1指向最后的None時，指針p2剛好指向倒數(shù)第N個node。重新連接指針p2所引用的節(jié)點即可。

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