lintcode 174. 删除链表中倒数第n个节点

难度：容易

1. Description

174. 删除链表中倒数第n个节点

2. Solution

• python
  pre_n指向的位置在cur指向位置的前面第n个。
  当cur是链表尾部时，pre_n正好是倒数第n个。

"""
Definition of ListNode
class 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 n==1:
            if head.next is None:
                return None
            pre_n = head
            cur = head
            for i in range(n):
                cur = cur.next
            while cur.next is not None:
                pre_n = pre_n.next
                cur = cur.next
            pre_n.next = pre_n.next.next
            return head
        pre_n = head
        cur = head
        for i in range(n-1):
            cur = cur.next
        while cur.next is not None:
            pre_n = pre_n.next
            cur = cur.next
        pre_n.val = pre_n.next.val
        pre_n.next = pre_n.next.next
        return head

3. Reference

1. https://www.lintcode.com/problem/remove-nth-node-from-end-of-list/description?_from=ladder