Stretch Problem: Reorder List (medium)

This problem is optional. The problems above cover what the chapter teaches. This one is here for readers who want a harder linked list question, and nothing later in the course depends on it.

Problem Statement

You are given the head of a singly linked list. Reorder it so that the nodes come in this order:

first node, last node, second node, second to last node, third node, and so on.

Only the links may change. Do not swap the values inside the nodes, and do not create new nodes.

Return the head of the reordered list.

Examples

Example 1

• Input: head =