Reorder a Singly Linked List in L0→Ln→L1→Ln-1… Order

Starting with the head node head of a singly linked list, rearrange its nodes so they appear in this sequence: $$L0 \to Ln \to L1 \to Ln-1 \to L2 \to Ln-2 \to\ldots$$ Here, Li denotes the node originally at position i, while Ln denotes the list's final node. Constraints / requirements: Node contents must remain unchanged; perform the rearrangement by rewiring next links. Target O(1) auxiliary space. I/O convention (used by these tests) Input: a single line containing…