Reorder Linked List

Given a singly linked list, reorder it to be in the following pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → .... This reordering is a common exercise to test your understanding of linked list manipulation, including traversal, node manipulation, and potentially reversing a portion of the list.

Problem Description

You are given the head of a singly linked list. Your task is to reorder the list in-place such that the nodes alternate between the beginning and the end of the original list.

Specifically, if the original list is L0, L1, L2, ..., Ln-1, Ln, the reordered list should be L0, Ln, L1, Ln-1, L2, Ln-2, ....

Key Requirements:

• The reordering must be done in-place, meaning you should modify the existing linked list nodes and pointers without creating a new list.
• You should not copy node values into another data structure (like an array) and then rearrange them.

Expected Behavior:

• The reordering should continue until the middle of the list is reached. If the list has an odd number of nodes, the middle node will be placed in its final position.

Edge Cases:

• An empty list.
• A list with only one node.
• A list with two nodes.

Examples

Example 1:

Input: head = 1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3
Explanation:
The original list is 1, 2, 3, 4.
The reordered list is 1 (L0), 4 (L3), 2 (L1), 3 (L2).

Example 2:

Input: head = 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3
Explanation:
The original list is 1, 2, 3, 4, 5.
The reordered list is 1 (L0), 5 (L4), 2 (L1), 4 (L3), 3 (L2).

Example 3:

Input: head = 1
Output: 1
Explanation:
A list with a single node remains unchanged.

Constraints

• The number of nodes in the list is in the range [0, 5 * 10^4].
• The value of each node is an integer within the range [-1000, 1000].

Notes

• Consider how to efficiently find the middle of the linked list. A common approach involves using two pointers.
• Once you have split the list (or identified its middle), you will likely need to reverse the second half of the list.
• After reversing, you'll need to carefully interleave the nodes from the first half and the reversed second half.
• Pay close attention to the next pointers to ensure the list remains correctly linked after reordering.