:orphan:

Remove Nth Node From End of List
================================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Given the ``head`` of a linked list, remove the ``n``\ :sup:```th```
node from the end of the list and return its head.

 

**Example 1:**

|image1|

::


   Input: head = [1,2,3,4,5], n = 2
   Output: [1,2,3,5]

**Example 2:**

::


   Input: head = [1], n = 1
   Output: []

**Example 3:**

::


   Input: head = [1,2], n = 1
   Output: [1]

 

**Constraints:**

- The number of nodes in the list is ``sz``.
- ``1 <= sz <= 30``
- ``0 <= Node.val <= 100``
- ``1 <= n <= sz``

 

**Follow up:** Could you do this in one pass?

.. |image1| image:: https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg

.. highlight:: python

Pattern
-------
Linked List, Two Pointers

Solution
--------
First, iterate through the linked list and get its length :math:`l`. The
problem reduces to remove the :math:`i = l - n` th node.

There are 3 cases for deleting a node in a linked list:
1. Beginnning: Set ``head`` to ``head.next``.
2. Middle: Set ``prev.next = prev.next.next`` where ``prev`` is :math:`i - 1`th
node.
3. End: Set ``prev.next = None``` where ``prev`` is the penultimate node. Note
that this is equivalent to the middle case since ``Node = prev.next.next``.

Code
----

.. literalinclude:: ../problems/medium/remove-nth-node-from-end-of-list/remove_nth_node_from_end_of_list__approach_1.py
    :language: python
    :lines: 14-

Test
----
>>> from remove_nth_node_from_end_of_list__approach_1 import ListNode, removeNthFromEnd
>>> head = ListNode.from_list([1, 2, 3, 4, 5])
>>> removeNthFromEnd(head, 2).to_list()
[1, 2, 3, 5]
>>> head = ListNode.from_list([1])
>>> print(removeNthFromEnd(head, 1))
None
>>> head = ListNode.from_list([1, 2])
>>> removeNthFromEnd(head, 1).to_list()
[1]

Complexity
----------
| :math:`n` is the length of the linked list
| Time: :math:`O(n)` — two passes
| Auxiliary Space: :math:`O(1)`

.. autoclass:: remove_nth_node_from_end_of_list__approach_1.ListNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: remove_nth_node_from_end_of_list__approach_1.removeNthFromEnd