:orphan:

Reorder List
============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/reorder-list/

You are given the head of a singly linked-list. The list can be
represented as:

::


   L0 → L1 → … → Ln - 1 → Ln

*Reorder the list to be on the following form:*

::


   L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves
may be changed.

 

**Example 1:**

|image1|

::


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

**Example 2:**

|image2|

::


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

 

**Constraints:**

- The number of nodes in the list is in the range
  ``[1, 5 * 10``\ :sup:```4```\ ``]``.
- ``1 <= Node.val <= 1000``

.. |image1| image:: https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg

.. highlight:: python

Pattern
-------
Linked List, Two Pointers, Stack, Recursion

Approaches
----------

.. tab-set::

    .. tab-item:: Split And Merge

        **Code**

        .. literalinclude:: ../problems/medium/reorder-list/reorder_list__split_and_merge.py
            :language: python
            :lines: 13-

        **Test**

        >>> from reorder_list__split_and_merge import reorderList, ListNode
        >>> head = ListNode.from_list([1, 2, 3, 4])
        >>> reorderList(head)
        >>> head.to_list()
        [1, 4, 2, 3]
        >>> head = ListNode.from_list([1, 2, 3, 4, 5])
        >>> reorderList(head)
        >>> head.to_list()
        [1, 5, 2, 4, 3]

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

        .. autofunction:: reorder_list__split_and_merge.reorderList