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

<pre>
L<sub>0</sub> &rarr; L<sub>1</sub> &rarr; &hellip; &rarr; L<sub>n - 1</sub> &rarr; L<sub>n</sub>
</pre>

<p><em>Reorder the list to be on the following form:</em></p>

<pre>
L<sub>0</sub> &rarr; L<sub>n</sub> &rarr; L<sub>1</sub> &rarr; L<sub>n - 1</sub> &rarr; L<sub>2</sub> &rarr; L<sub>n - 2</sub> &rarr; &hellip;
</pre>

<p>You may not modify the values in the list&#39;s nodes. Only nodes themselves may be changed.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg" style="width: 422px; height: 222px;" />
<pre>
<strong>Input:</strong> head = [1,2,3,4]
<strong>Output:</strong> [1,4,2,3]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg" style="width: 542px; height: 222px;" />
<pre>
<strong>Input:</strong> head = [1,2,3,4,5]
<strong>Output:</strong> [1,5,2,4,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the list is in the range <code>[1, 5 * 10<sup>4</sup>]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 1000</code></li>
</ul>

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # maintain memory efficiency -> avoid creating new Node instances
        # iterate through whole list first and create a map with references to the node
            # that corresponds to each index
        node_map = {} # index -> node instance
        curr = head
        index = 0
        while curr is not None:
            node_map[index] = curr
            curr = curr.next
            index += 1
        # The number of edges that need to change is floor divide length of list by 2
        n = len(node_map.keys())
        edges_to_changes = n//2
        # change edges of node 0 to length num edges computed in previous comment
        for e in range(edges_to_changes):
            # 1. save node e's next pointer
            old = node_map[e].next
            # 2. change node e's next pointer to node n-e
            node_map[e].next = node_map[n - e - 1]
            # 3. change node n-e's next pointer to the saved next pointer in step 1
            node_map[n - e - 1].next = old
        # change last e + 1 next pointer to None
        node_map[edges_to_changes].next = None

        return node_map[0]
24300