题目描述：

 

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

 注意事项

链表中的节点个数大于等于n

您在真实的面试中是否遇到过这个题？ 

Yes

 

样例

给出链表1->2->3->4->5->null和 n = 2.

删除倒数第二个节点之后，这个链表将变成1->2->3->5->null.

 

O(n)时间复杂度

 

 

 

题目分析：

 

创建两个指针，head指向表头、curent指向链表第n个元素；

循环后移n次，直至curent=Null，此时head指向倒数第n个元素。

O(n)时间复杂度

 

源码：

"""Definition of ListNodeclass ListNode(object):    def __init__(self, val, next=None):        self.val = val        self.next = next"""class Solution:    """    @param head: The first node of linked list.    @param n: An integer.    @return: The head of linked list.    """    def removeNthFromEnd(self, head, n):        # write your code here        if head is None: return None        if n == 0: return head        cur = head        follow = head        pre = head        for i in range(n):            follow = follow.next        # 当follow为null时，此时链表长度等于n，删除第一个元素即可        if follow is None:            return cur.next        # 将pre和fol依次后移，实际后移次数为n-1            while follow.next is not None:            follow = follow.next            cur = pre            pre = pre.next        # 删除第n个元素        pre.next = pre.next.next        return head