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.

&nbsp;
Example 1:

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


Example 2:

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


&nbsp;
Constraints:


	The number of nodes in the list is in the range [1, 5 * 104].
	1 &lt;= Node.val &lt;= 1000


class Solution:
    def reverse(self , head):
        prev = None
        after = None
        curr = head
        while(curr):
            after = curr.next
            curr.next = prev
            prev = curr
            curr = after
        return prev
            
    def find_middle(self , head):
        slow = head
        fast = head
        while(fast and fast.next):
            fast = fast.next.next
            slow = slow.next
        return slow
        
    def reorderList(self, head: Optional[ListNode]) -> None:
        mid = self.find_middle(head)
        rev = self.reverse(mid)
        first = head
        second = rev
        
        while(second.next):
            temp = first.next
            first.next = second
            first = temp
            
            temp = second.next
            second.next = first
            second = temp
            
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
		
		// Find start of second list
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
		
        ListNode list1 = head;
        ListNode list2 = reverseList(slow.next); // slow.next is start of list2
        
        // Break first list from second list!
        slow.next = null; 
        
		// Merge list1 and list2
        while (list2 != null) {
            ListNode l1Next = list1.next;
            ListNode l2Next = list2.next;
            list2.next = list1.next;
            list1.next = list2;
            list1 = l1Next;
            list2 = l2Next;
        }
    }
    
    private ListNode reverseList(ListNode node) {
        if (node == null) return node;
        ListNode newHead = null, currNode = node;
        while (currNode != null) {
            ListNode backup = currNode.next;
            currNode.next = newHead;
            newHead = currNode;
            currNode = backup;
        }
        return newHead;
    }
}
class Solution {
public:
    ListNode* solve(ListNode* head,ListNode* temp){
        if(temp==NULL)return head;
        ListNode* curr=solve(head,temp->next);
        if(!curr)return NULL;
        if(curr==temp){
            curr->next=NULL;
            return nullptr;
        }
        if(curr->next==temp){
            temp->next=nullptr;
            return NULL;
        }
        temp->next=curr->next;
        curr->next=temp;
        curr=temp->next;
        return curr;
    }
    void reorderList(ListNode* head) {
        solve(head,head);
    }
};
var reorderList = function(head) {
    const dummyL = new ListNode(-1);
    const dummyR = new ListNode(-1);

    let currL = dummyL;
    let currR = dummyR;
    let past = false;

    let fast = head;
    let slow = head;
    while (slow) {
        if (!fast?.next) {
            past = true
        }

        if (past) {
            currR.next = slow;
            currR = slow;
        } else {
            currL.next = slow
            currL = slow;
        }

        if (fast) {
            fast = fast.next?.next || null;
        }
        slow = slow.next
    }
    currL.next = null;
    currR.next = null;

    dummyR.next = reverse(dummyR.next);
    return merge(dummyL.next, dummyR.next);
};

const merge = (l, r) => {
    const dummy = new ListNode(-1);

    let currL = l;
    let currR = r;
    let last = dummy;

    let count = 0;
    while (currL && currR) {
        if (count % 2 === 0) {
            last.next = currL;
            last = currL;
            currL = currL.next
        } else {
            last.next = currR;
            last = currR;
            currR = currR.next
        }

        count++
    }

    last.next = (currL || currR);
    return dummy.next;
}

const reverse = (head) => {
    let prev = null;
    let curr = head;
    while (curr) {
        const tempPrev = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tempPrev;
    }

    return prev;
}
Reorder List