Reorder List: the idea to remember.

The core insight

Find the midpoint, detach and reverse the second half, then interleave the two halves.

Why it works

After reversal, both required output orders are available from the fronts of the two lists. Alternating them constructs the target order.

The mistake to avoid

Detach the first half before weaving or old links can create cycles. Handle odd and even lengths.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode current = slow.next, reversed = null; slow.next = null;
    while (current != null) {
        ListNode next = current.next; current.next = reversed; reversed = current; current = next;
    }
    ListNode first = head;
    while (reversed != null) {
        ListNode a = first.next, b = reversed.next;
        first.next = reversed; reversed.next = a; first = a; reversed = b;
    }
}

Make the next connection