移除链表倒数第n个元素

Remove Nth Node From End of List

• 给定一个链表，移除倒数第n个元素，返回链表头部。

• Given a linked list, remove the nth node from the end of list and return its head.

Note:

example 1

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.

example 2

Given linked list: 1, and n = 1.output: None

example 3

Given linked list: 1->2->3, and n = 3.output: 2->3

思路

1. 两个指针，fast和slow，fast指向slow之后n个位置，同步移动fast和slow，当fast.next为null的时候，slow.next即为要移除的那个元素，只需要slow.next = slow.next.next即可，时间复杂度O(n)

2. 注意考虑n为链表长度的情况，即移除首个元素

代码

# Definition for singly-linked list.class ListNode(object):    def __init__(self, x):        self.val = x        self.next = Noneclass Solution(object):    def removeNthFromEnd(self, head, n):        """        :type head: ListNode        :type n: int        :rtype: ListNode        """        a = b = head        for i in range(n):            b = b.next        if not b:            return head.next        while b.next:            a = a.next            b = b.next        a.next = a.next.next        return head

本题以及其它leetcode题目代码github地址: