text: #!/usr/bin/env python
  # -*- coding: utf-8 -*-
  
  """
  __project__ =  'leetcode'
  __file__    =  '__init__.py'
  __author__  =  'king'
  __time__    =  '2019/11/15 09:53'
  
  
                                _ooOoo_
                               o8888888o
                               88" . "88
                               (| -_- |)
                               O\  =  /O
                            ____/`---'\____
                          .'  \\|     |//  `.
                         /  \\|||  :  |||//  \
                        /  _||||| -:- |||||-  \
                        |   | \\\  -  /// |   |
                        | \_|  ''\---/''  |   |
                        \  .-\__  `-`  ___/-. /
                      ___`. .'  /--.--\  `. . __
                   ."" '<  `.___\_<|>_/___.'  >'"".
                  | | :  `- \`.;`\ _ /`;.`/ - ` : | |
                  \  \ `-.   \_ __\ /__ _/   .-` /  /
             ======`-.____`-.___\_____/___.-`____.-'======
                                `=---='
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                         佛祖保佑        永无BUG
  """
  from leetcode.lessons.linked_list import ListNode
  from leetcode.utils.timeutils import time_interval
  
  '''
  难度：中等
  给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。
  
  示例：
      给定一个链表: 1->2->3->4->5, 和 n = 2.
  
  当删除了倒数第二个节点后，链表变为 1->2->3->5.
  说明：
      给定的 n保证是有效的。
  
  进阶：
      你能尝试使用一趟扫描实现吗？
  '''
  
  
  class Solution(object):
      @time_interval
      def removeNthFromEnd(self, head, n):
          """
          :type head: ListNode
          :type n: int
          :rtype: ListNode
          """
          x = y = head
          for i in range(n):
              x = x.next
          if not x:
              return head.next
          while x.next:
              x = x.next
              y = y.next
          y.next = y.next.next
          return head
  
  
  l1 = ListNode.generate([1, 2, 3, 4, 5])
  
  print(Solution().removeNthFromEnd(l1, 2))
  