:orphan:

Reverse Linked List
===================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/reverse-linked-list/

Given the ``head`` of a singly linked list, reverse the list, and return
*the reversed list*.

 

**Example 1:**

|image1|

::


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

**Example 2:**

|image2|

::


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

**Example 3:**

::


   Input: head = []
   Output: []

 

**Constraints:**

- The number of nodes in the list is the range ``[0, 5000]``.
- ``-5000 <= Node.val <= 5000``

 

**Follow up:** A linked list can be reversed either iteratively or
recursively. Could you implement both?

.. |image1| image:: https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg

.. highlight:: python

Pattern
-------
Linked List, Recursion

Solution
--------
Track the current ``node`` and ``prev`` node. At each step, store ``node.next``
in a temporary variable. Set ``node.next`` to ``prev`` and then advance
``prev`` and ``node``.

Code
----

.. literalinclude:: ../problems/easy/reverse-linked-list/reverse_linked_list__approach_1.py
    :language: python
    :lines: 14-

Test
----
>>> from reverse_linked_list__approach_1 import ListNode, reverseList
>>> head = ListNode.from_list([1, 2, 3, 4, 5])
>>> reverseList(head).to_list()
[5, 4, 3, 2, 1]
>>> head = ListNode.from_list([1, 2])
>>> reverseList(head).to_list()
[2, 1]
>>> head = ListNode.from_list([1])
>>> reverseList(head).to_list()
[1]

Complexity
----------
| :math:`n` is the number of nodes in the linked list
| Time: :math:`O(n)` — single pass through the list
| Auxiliary Space: :math:`O(1)`

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

.. autofunction:: reverse_linked_list__approach_1.reverseList