Given a linked list, remove the n-th node from the end of list and return its head.
Example: Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note: Given n will always be valid.
Follow up: Could you do this in one pass?
思路
我们采用两个指针和哨兵模式来解决这个问题。 一开始先将快指针向前移动N位，然后和慢指针一起移动，直到指针指向最后一位结束。然后将漫指针的next指针重新赋值，就可以将对应节点删除。
时间复杂度为O(n)， 空间复杂度为O(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
"""
if not head or n == 0:
return head
res = second = first = ListNode(0) # 构建哨兵节点
first.next = head
while n > 0: # 移动快指针
first = first.next
n -= 1
while first.next: # 移动快慢指针
second = second.next
first = first.next
second.next = second.next.next # 删除指定节点
return res.next