<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.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head == NULL || head->next == NULL)
        return;
        
        vector<int> temp;
        ListNode* curr=head;
        while(curr!=NULL)
        {
            temp.push_back(curr->val);
            curr = curr->next;
        }
        ListNode* nhead=NULL;
        ListNode* ntail=NULL;
        for(int i=0;i<temp.size()/2; i++)
        {
            ListNode* curr=new ListNode(temp[i]);
            if(nhead == NULL)
            {
                nhead = curr;
                ntail = curr;
            }
            else
            {
                ntail->next = curr;
                ntail=ntail->next;
            }

            ListNode* curr1=new ListNode(temp[temp.size()-i-1]);
            ntail->next = curr1;
            ntail=ntail->next;

        }
        if (temp.size() % 2 != 0) {
            ListNode* newNode = new ListNode(temp[temp.size()/2]);
            ntail->next = newNode;
            ntail = ntail->next;
        }
        ntail->next = NULL;

        *head = *nhead;

    }
};
25300