<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.

        # if even, elements till (len/2 - 1)   index on leftside
        # if odd, elements till  (len//2 + 1 ) index on leftside
        # use double ptrs, fast one will reach end of list, track elements after mid for fast one, then add from that list in reverse order to elements till mid in   
        tmp=head
        length=0
        while tmp!=None:
            tmp=tmp.next
            length+=1

        if length<=2:  #no change required
            return

        if length%2==0:
            reqidx = (length/2 ) - 1
        else:
            reqidx = (length//2)
        print("length",length, "elems on left arr",reqidx+1)


        i=0
        j=0
        slow = head
        fast = head
        if length%2!=0:
            j=1
            fast=head.next
        slowvalues = []
        fastvalues = []
        while fast!=None and fast.next!=None:
            # print("i=",i,"  j=",j)
            if i<=reqidx:
                slowvalues.append(slow.val)
            if j>reqidx:
                fastvalues.append(fast.val)
                if fast.next is not None and fast.next.next is None:
                    fastvalues.append(fast.next.val)
           
            slow = slow.next
            i+=1
           
            if length%2!=0:
                if j==reqidx:
                    fast = fast.next
                    if fast.next is None:
                        fastvalues.append(fast.val)
                    j+=1
                    continue
                # else:
                #     if j>reqidx:
                #         fast = fast.next
                #         j+=1
                #     else:
                #         fast = fast.next.next
                #         j+=2
                   
            # else:
            #     if j>reqidx:
            #         fast = fast.next
            #         j+=1
            #     else:
            #         fast = fast.next.next
            #         j+=2
            if j>reqidx:
                fast = fast.next
                j+=1
            else:
                fast = fast.next.next
                j+=2
            

        if length%2!=0:
            slowvalues.append(slow.val)
            # if len(slowvalues) + len(fastvalues)!= length:
            #     fastvalues.append(fast.val)

        print(len(slowvalues), len(fastvalues))
        print("slow...",slowvalues)
        fastvalues = fastvalues[::-1]
        print("fast...",fastvalues)

        finalvals = []
        tmp = head
        for i in range(len(slowvalues)):
            finalvals.append(slowvalues[i])
            if i>0:
                tmp.next = ListNode(val=slowvalues[i])
                tmp = tmp.next

            try:
                if fastvalues[i] is not None:
                    finalvals.append(fastvalues[i])
                    tmp.next = ListNode(val=fastvalues[i])
                    tmp  = tmp.next
            except IndexError:
                print("odd-len-so-index-error")
                break
        
        print("total ... ",finalvals)


    
23900